#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_probing_strategies.hh"
#include "BLI_vector.hh"
#include "BLI_vector_set_slots.hh"

Classes
class	blender::VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >
struct	blender::CustomIDHash< T, GetIDFn >
struct	blender::CustomIDEqual< T, GetIDFn >

Namespaces
namespace	blender

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

Typedefs
template<typename Key, int64_t InlineBufferCapacity = 4, typename ProbingStrategy = DefaultProbingStrategy, typename Hash = DefaultHash<Key>, typename IsEqual = DefaultEquality<Key>, typename Slot = typename DefaultVectorSetSlot<Key>::type>
using	blender::RawVectorSet
template<typename T, typename GetIDFn, int64_t InlineBufferCapacity = 4>
using	blender::CustomIDVectorSet

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.