Blender
V3.3
|
#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.
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 > |
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:
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 map uses strings as keys.print_stats
method can be used to get information about the distribution of keys and memory usage of the map.Definition in file BLI_map.hh.
#define LOAD_FACTOR 1, 2 |
The max load factor is 1/2 = 50% by default.
Definition at line 139 of file BLI_map.hh.
Iterate over a slot index sequence for a given hash.
Definition at line 152 of file BLI_map.hh.
#define MAP_SLOT_PROBING_END | ( | ) | SLOT_PROBING_END() |
Definition at line 155 of file BLI_map.hh.