Blender  V3.3
Classes | Namespaces | Macros | Typedefs
BLI_map.hh File Reference
#include <optional>
#include <unordered_map>
#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_map_slots.hh"
#include "BLI_probing_strategies.hh"

Go to the source code of this file.

Classes

class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >
 
struct  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::BaseIterator
 
class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::BaseIteratorRange< SubIterator >
 
class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::KeyIterator
 
class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::ValueIterator
 
class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::MutableValueIterator
 
struct  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::Item
 
struct  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::MutableItem
 
class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::ItemIterator
 
class  blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::MutableItemIterator
 
class  blender::StdUnorderedMapWrapper< Key, Value >
 

Namespaces

 blender
 

Macros

#define LOAD_FACTOR   1, 2
 
#define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT)
 
#define MAP_SLOT_PROBING_END()   SLOT_PROBING_END()
 

Typedefs

template<typename Key , typename Value , int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) + sizeof(Value)), typename ProbingStrategy = DefaultProbingStrategy, typename Hash = DefaultHash<Key>, typename IsEqual = DefaultEquality, typename Slot = typename DefaultMapSlot<Key, Value>::type>
using blender::RawMap = Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator >
 

Detailed Description

A blender::Map<Key, Value> is an unordered associative container that stores key-value pairs. The keys have to be unique. It is designed to be a more convenient and efficient replacement for std::unordered_map. All core operations (add, lookup, remove and contains) can be done in O(1) amortized expected time.

Your default choice for a hash map in Blender should be blender::Map.

blender::Map 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 a Key and Value instance.

Benchmarking 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, data types, slot type and 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_map_test.cc. The results of that benchmark are there as well. The numbers show that in this specific case blender::Map outperforms std::unordered_map consistently by a good amount.

Some noteworthy information:

Definition in file BLI_map.hh.

Macro Definition Documentation

◆ LOAD_FACTOR

#define LOAD_FACTOR   1, 2

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

Definition at line 139 of file BLI_map.hh.

◆ MAP_SLOT_PROBING_BEGIN

#define MAP_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 152 of file BLI_map.hh.

◆ MAP_SLOT_PROBING_END

#define MAP_SLOT_PROBING_END ( )    SLOT_PROBING_END()

Definition at line 155 of file BLI_map.hh.