Blender  V3.3
Classes | Namespaces | Macros | Typedefs
BLI_vector_set.hh File Reference
#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_probing_strategies.hh"
#include "BLI_vector_set_slots.hh"

Go to the source code of this file.

Classes

class  blender::VectorSet< Key, ProbingStrategy, Hash, IsEqual, Slot, Allocator >
 

Namespaces

 blender
 

Macros

#define LOAD_FACTOR   1, 2
 
#define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
 
#define VECTOR_SET_SLOT_PROBING_END()   SLOT_PROBING_END()
 

Typedefs

template<typename Key , typename ProbingStrategy = DefaultProbingStrategy, typename Hash = DefaultHash<Key>, typename IsEqual = DefaultEquality, typename Slot = typename DefaultVectorSetSlot<Key>::type>
using blender::RawVectorSet = VectorSet< Key, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator >
 

Detailed Description

A blender::VectorSet<Key> is an ordered container for elements of type Key. It has the same interface as blender::Set with the following extensions:

All core operations (add, remove and contains) can be done in O(1) amortized expected time.

Using a VectorSet instead of a normal Set can be beneficial in any of the following circumstances:

blender::VectorSet is implemented using open addressing in a slot array with a power-of-two size. Other than in blender::Set, a slot does not contain the key though. Instead it only contains an index into an array of keys that is stored separately.

Some noteworthy information:

Possible Improvements:

Definition in file BLI_vector_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 126 of file BLI_vector_set.hh.

◆ VECTOR_SET_SLOT_PROBING_BEGIN

#define VECTOR_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 145 of file BLI_vector_set.hh.

◆ VECTOR_SET_SLOT_PROBING_END

#define VECTOR_SET_SLOT_PROBING_END ( )    SLOT_PROBING_END()

Definition at line 148 of file BLI_vector_set.hh.