carb::container::RHUnorderedMap

Defined in carb/container/RHUnorderedMap.h

template<class Key, class Value, class Hasher = std::hash<Key>, class Equals = std::equal_to<Key>, size_t LoadFactorMax100 = 80> class RHUnorderedMap : public detail::RobinHood<80, Key, std::pair<const Key, Value>, detail::Select1st<Key, std::pair<const Key, Value>>, std::hash<Key>, std::equal_to<Key>>

Implements an Unordered Map, that is: a container that contains a mapping of keys to values where all keys must be unique.

There is no defined order to the set of keys.

In an open-addressing (“OA”) hash table, the contained items are stored in the buckets directly. Contrast this with traditional hash tables that typically have a level of indirection: buckets point to the head of a linked-list that contains every item that hashes to that bucket. Open-addressing hash tables are great for using contiguous memory, whereas traditional hash tables have a separate allocation per node and fragment memory. However, OA hash tables have a couple downsides: if a collision occurs on insertion, probing must happen until an open spot is found where the item can be placed. For a find operation, probing must continue until an empty spot is reached to make sure that all keys have been checked. When erasing an item, a “deleted” marker must be put in its place so that probing past the key can continue. This system also gives advantage to earlier insertions and penalizes later collisions.

The Robin Hood algorithm for open-addressing hashing was first postulated by Pedro Celis in 1986: https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf. Simply put, it applies a level of fairness to locality of items within the OA hash table. This is done by tracking the distance from an items ideal insertion point. Similarly the distance-from-ideal can be easily computed for existing locations that are probed. Once a probed location for a new item will cause the new item to be worse off (farther from ideal insertion) than the existing item, the new item can “steal” the location from the existing item, which must then probe until it finds a location where it is worse off than the existing item, and so on. This balancing of locality has beneficial side effects for finding and erasing too: when searching for an item, once a location is reached where the item would be worse off than the existing item, probing can cease with the knowledge that the item is not contained.

OA hash tables cannot be direct drop-in replacements for closed-addressing hash containers such as std::unordered_map as nearly every modification to the table can potentially invalidate any other iterator.

Open-addressing hash tables may not be a good replacement for std unordered containers in cases where the key and/or value is very large (though this may be mitigated somewhat by using indirection through std::unique_ptr). Since OA hash tables must carry the size of each value_type, having a low load factor (or a high capacity() to size() ratio) wastes a lot of memory, especially if the key/value pair is very large.

It is important to keep OA hash tables as compact as possible, as operations like clear() and iterating over the hash table are O(n) over capacity(), not size(). You can always ensure that the hash table is as compact as possible by calling rehash(0).

Because of the nature of how elements are stored in this hash table, there are two iterator types: iterator and find_iterator (both with const versions). These types can be compared with each other, but incrementing these objects works differently. iterator and const_iterator traverse to the next item in the container, while find_iterator and const_find_iterator will only traverse to the next item with the same key. In multi-key containers, items with the same key may not necessarily be stored adjacently, so incrementing iterator may not encounter the next item with the same key as the previous. For unique-key containers, incrementing a find_iterator will always produce end() since keys are guaranteed to be unique.

Iterator/reference/pointer invalidation (note differences from std::unordered_map): Operation | Invalidates ——— | ——–— All read operations: Never clear, rehash, reserve, operator=, insert, emplace, try_emplace, operator[] | Always erase | Only the element removed swap | All iterators, no pointers/references

Warning

This container is similar to, but not a drop-in replacement for std::unordered_map due to differences in iterator invalidation and memory layout.

Template Parameters

Key – The key type
Value – The mapped type to be associated with Key
Hasher – A functor to use as a hashing function for Key
Equals – A functor to use to compare two Key values for equality
LoadFactorMax100 – The load factor to use for the table. This value must be in the range [10, 100] and represents the percentage of entries in the hash table that will be filled before resizing. Open-addressing hash maps with 100% usage have better memory usage but worse performance since they need “gaps” in the hash table to terminate runs.

Public Types

using key_type = typename Base::key_type: The key type.

using mapped_type = Value : The mapped value type.

using value_type = typename Base::value_type: The value type (effectively std::pair<const key_type, mapped_type>)

using size_type = typename Base::size_type: Unsigned integer type (typically size_t)

using difference_type = typename Base::difference_type: Signed integer type (typically ptrdiff_t)

using hasher = typename Base::hasher: The hash function.

using key_equal = typename Base::key_equal: The key-equals function.

using reference = typename Base::reference: value_type&

using const_reference = typename Base::const_reference: const value_type&

using pointer = typename Base::pointer: value_type*

using const_pointer = typename Base::const_pointer: const value_type*

using iterator = typename Base::iterator: A LegacyForwardIterator to value_type.

using const_iterator = typename Base::const_iterator: A LegacyForwardIterator to const value_type

using find_iterator = typename Base::find_iterator: A LegacyForwardIterator to value_type that proceeds to the next matching key when incremented.

using const_find_iterator = typename Base::const_find_iterator: A LegacyForwardIterator to const value_type that proceeds to the next matching key when incremented.

Public Functions

constexpr RHUnorderedMap() noexcept = default: Constructs empty container.

inline RHUnorderedMap(const RHUnorderedMap &other)

Copy constructor.

Copies elements from another container.

Note

*this may have a different carb::container::detail::RobinHood::capacity() than other.

Parameters: other – The other container to copy entries from.

inline RHUnorderedMap(RHUnorderedMap &&other)

Move constructor.

Moves elements from another container.

Note

No move constructors on contained elements are invoked. other will be carb::container::detail::RobinHood::empty() after this operation.

Parameters: other – The other container to move entries from.

~RHUnorderedMap() = default

Destructor.

Destroys all contained elements and frees memory.

inline RHUnorderedMap &operator=(const RHUnorderedMap &other)

Copy-assign operator.

Destroys all currently stored elements and copies elements from another container.

Parameters: other – The other container to copy entries from.
Returns: *this

inline RHUnorderedMap &operator=(RHUnorderedMap &&other)

Move-assign operator.

Effectively swaps with another container.

Parameters: other – The other container to copy entries from.
Returns: *this

inline std::pair<iterator, bool> insert(const value_type &value)

Inserts an element into the container.

If insertion is successful, all iterators, references and pointers are invalidated.

Parameters: value – The value to insert by copying.
Returns: A pair consisting of an iterator to the inserted element (or the existing element that prevented the insertion) and a bool that will be true if insertion took place or false if insertion did not take place.

inline std::pair<iterator, bool> insert(value_type &&value)

Inserts an element into the container.

If insertion is successful, all iterators, references and pointers are invalidated.

Parameters: value – The value to insert by moving.
Returns: A pair consisting of an iterator to the inserted element (or the existing element that prevented the insertion) and a bool that will be true if insertion took place or false if insertion did not take place.

template<class P> inline std::pair<iterator, bool> insert(std::enable_if_t<std::is_constructible<value_type, P&&>::value, P&&> value)

Inserts an element into the container.

Only participates in overload resolution if std::is_constructible_v<value_type, P&&> is true.

If insertion is successful, all iterators, references and pointers are invalidated.

Parameters: value – The value to insert by constructing via std::forward<P>(value).
Returns: A pair consisting of an iterator to the inserted element (or the existing element that prevented the insertion) and a bool that will be true if insertion took place or false if insertion did not take place.

template<class ...Args> inline std::pair<iterator, bool> emplace(Args&&... args)

Constructs an element in-place.

If insertion is successful, all iterators, references and pointers are invalidated.

Parameters: args – The arguments to pass to the value_type constructor.
Returns: A pair consisting of an iterator to the inserted element (or the existing element that prevented the insertion) and a bool that will be true if insertion took place or false if insertion did not take place.

template<class ...Args> inline std::pair<iterator, bool> try_emplace(const key_type &key, Args&&... args)

Inserts in-place if the key does not exist; does nothing if the key already exists.

Inserts a new element into the container with key key and value constructed with args if there is no element with the key in the container. If the key does not exist and the insert succeeds, constructs value_type as value_type{std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(std::forward<Args>(args)...}.

Parameters

key – The key used to look up existing and insert if not found.
args – The args used to construct mapped_type.

Returns

A pair consisting of an iterator to the inserted element (or the existing element that prevented the insertion) and a bool that will be true if insertion took place or false if insertion did not take place.

template<class ...Args> inline std::pair<iterator, bool> try_emplace(key_type &&key, Args&&... args)

Inserts in-place if the key does not exist; does nothing if the key already exists.

Inserts a new element into the container with key key and value constructed with args if there is no element with the key in the container. If the key does not exist and the insert succeeds, constructs value_type as value_type{std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::forward_as_tuple(std::forward<Args>(args)...}.

Parameters

key – The key used to look up existing and insert if not found.
args – The args used to construct mapped_type.

Returns

A pair consisting of an iterator to the inserted element (or the existing element that prevented the insertion) and a bool that will be true if insertion took place or false if insertion did not take place.

inline size_type erase(const key_type &key)

Removes elements with the given key.

References, pointers and iterators to the erase element are invalidated. All other iterators, pointers and references remain valid.

Parameters: key – the key value of elements to remove
Returns: the number of elements removed (either 1 or 0).

inline mapped_type &at(const key_type &key)

Access specified element with bounds checking.

This function is only available if exceptions are enabled.

Parameters: key – The key of the element to find.
Throws: std::out_of_range – if no such element exists.
Returns: a reference to the mapped value of the element with key equivalent to key.

inline const mapped_type &at(const key_type &key) const

Access specified element with bounds checking.

This function is only available if exceptions are enabled.

Parameters: key – The key of the element to find.
Throws: std::out_of_range – if no such element exists.
Returns: a reference to the mapped value of the element with key equivalent to key.

inline mapped_type &operator[](const key_type &key)

Returns a reference to a value that is mapped to the given key, performing an insertion if such key does not already exist.

If key does not exist, inserts a value_type constructed in-place from std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>().

key_type must be CopyConstructible and mapped_type must be DefaultConstructible.

Parameters: key – the key of the element to find or insert
Returns: a reference to the mapped_type mapped to key.

inline mapped_type &operator[](key_type &&key)

Returns a reference to a value that is mapped to the given key, performing an insertion if such key does not already exist.

If key does not exist, inserts a value_type constructed in-place from std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>().

key_type must be CopyConstructible and mapped_type must be DefaultConstructible.

Parameters: key – the key of the element to find or insert
Returns: a reference to the mapped_type mapped to key.

inline size_t count(const key_type &key) const

Returns the number of elements matching the specified key.

Parameters: key – The key to check for.
Returns: The number of elements with the given key (either 1 or 0).