BLI_map.hh File Reference

#include <optional>
#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
struct	blender::MapItem< Key, Value >
struct	blender::MutableMapItem< Key, Value >
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
class	blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::ItemIterator
class	blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::MutableItemIterator

Namespaces
namespace	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<Key>, typename Slot = typename DefaultMapSlot<Key, Value>::type>
using	blender::RawMap

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:

• Key and Value must be movable types.
• Pointers to keys and values might be invalidated when the map 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_map_slots.hh for details.
• Small buffer optimization is enabled by default, if Key and Value are not too large.
• 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.
• There are multiple methods to add and lookup keys for different use cases.
• You cannot use a range-for loop on the map directly. Instead use the keys(), values() and items() iterators. If your map is non-const, you can also change the values through those iterators (but not the keys).
• 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 map uses strings as keys.
• The default constructor is cheap, even when a large InlineBufferCapacity is used. A large slot array will only be initialized when the first element is added.
• The print_stats method can be used to get information about the distribution of keys and memory usage of the map.
• The method names don't follow the std::unordered_map names in many cases. Searching for such names in this file will usually let you discover the new name.

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

Iterate over a slot index sequence for a given hash.

Definition at line 175 of file BLI_map.hh.

MAP_SLOT_PROBING_END

#define MAP_SLOT_PROBING_END

(

)

SLOT_PROBING_END()

Definition at line 178 of file BLI_map.hh.