Blender  V3.3
Classes | Namespaces | Macros | Typedefs
BLI_set.hh File Reference
#include <unordered_set>
#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_probing_strategies.hh"
#include "BLI_set_slots.hh"

Go to the source code of this file.

Classes

class  blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >
 
class  blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::Iterator
 
class  blender::StdUnorderedSetWrapper< Key >
 

Namespaces

 blender
 

Macros

#define LOAD_FACTOR   1, 2
 
#define SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
 
#define SET_SLOT_PROBING_END()   SLOT_PROBING_END()
 

Typedefs

template<typename Key , int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)), typename ProbingStrategy = DefaultProbingStrategy, typename Hash = DefaultHash<Key>, typename IsEqual = DefaultEquality, typename Slot = typename DefaultSetSlot<Key>::type>
using blender::RawSet = Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator >
 

Detailed Description

A blender::Set<Key> is an unordered container for unique elements of type Key. It is designed to be a more convenient and efficient replacement for std::unordered_set. All core operations (add, remove and contains) can be done in O(1) amortized expected time.

In most cases, your default choice for a hash set in Blender should be blender::Set.

blender::Set is implemented using open addressing in a slot array with a power-of-two size. Every slot is in one of three states: empty, occupied or removed. If a slot is occupied, it contains an instance of the key type.

Bench-marking and comparing hash tables is hard, because many factors influence the result. The performance of a hash table depends on the combination of the hash function, probing strategy, max load factor, key type, slot type and the data distribution. This implementation is designed to be relatively fast by default in all cases. However, it also offers many customization points that allow it to be optimized for a specific use case.

A rudimentary benchmark can be found in BLI_set_test.cc. The results of that benchmark are there as well. The numbers show that in this specific case blender::Set outperforms std::unordered_set consistently by a good amount.

Some noteworthy information:

Possible Improvements:

Definition in file BLI_set.hh.

Macro Definition Documentation

◆ LOAD_FACTOR

#define LOAD_FACTOR   1, 2

The max load factor is 1/2 = 50% by default.

Definition at line 145 of file BLI_set.hh.

◆ SET_SLOT_PROBING_BEGIN

#define SET_SLOT_PROBING_BEGIN (   HASH,
  R_SLOT 
)
Value:
SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
auto &R_SLOT = slots_[SLOT_INDEX];
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define HASH(i, j, k)

Iterate over a slot index sequence for a given hash.

Definition at line 158 of file BLI_set.hh.

◆ SET_SLOT_PROBING_END

#define SET_SLOT_PROBING_END ( )    SLOT_PROBING_END()

Definition at line 161 of file BLI_set.hh.