Blender
V3.3
|
#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 > |
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:
add_new
and remove_contained
should be used instead of add
and remove
whenever appropriate. Assumptions and intention are described better this way._as
. The template parameters Hash and IsEqual have to support the other key type. This can greatly improve performance when the strings are used as keys.print_stats
method can be used to get information about the distribution of keys and memory usage.Possible Improvements:
Definition in file BLI_vector_set.hh.
#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.
Iterate over a slot index sequence for a given hash.
Definition at line 145 of file BLI_vector_set.hh.
#define VECTOR_SET_SLOT_PROBING_END | ( | ) | SLOT_PROBING_END() |
Definition at line 148 of file BLI_vector_set.hh.