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
namespace	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<Key>, 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:

• The insertion order of keys is maintained as long as no elements are removed.
• The keys are stored in a contiguous array.

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:

• The insertion order is important.
• Iteration over all keys has to be fast.
• The keys in the set are supposed to be passed to a function that does not have to know that the keys are stored in a set. With a VectorSet, one can get a Span containing all keys without additional copies.

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:

• Key must be a movable type.
• Pointers to keys might be invalidated, when the vector set is changed or moved.
• The hash function can be customized. See BLI_hash.hh for details.
• The probing strategy can be customized. See BLI_probing_strategies.hh for details.
• The slot type can be customized. See BLI_vector_set_slots.hh for details.
• The methods add_new and remove_contained should be used instead of add and remove whenever appropriate. Assumptions and intention are described better this way.
• Using a range-for loop over a vector set, is as efficient as iterating over an array (because it is the same thing).
• Lookups can be performed using types other than Key without conversion. For that use the methods ending with _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.
• The default constructor is cheap.
• The print_stats method can be used to get information about the distribution of keys and memory usage.

Possible Improvements:

• Small buffer optimization for the keys.

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 128 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];

Iterate over a slot index sequence for a given hash.

Definition at line 147 of file BLI_vector_set.hh.

VECTOR_SET_SLOT_PROBING_END

#define VECTOR_SET_SLOT_PROBING_END

(

)

SLOT_PROBING_END()

Definition at line 150 of file BLI_vector_set.hh.