RHUnorderedMap#

Fully qualified name: carb::container::RHUnorderedMap

Defined in carb/container/RHUnorderedMap.h

template<typename Key, typename Value, typename Hasher = std::hash<Key>, typename Equals = std::equal_to<Key>, size_t LoadFactorMax100 = kDefaultLoadFactor, typename Allocator = std::allocator<std::pair<const Key, Value>>> class RHUnorderedMap : public detail::RobinHood<detail::RobinHoodMapTraits<Key, Value, std::hash<Key>, std::equal_to<Key>, std::allocator<std::pair<const Key, Value>>, kDefaultLoadFactor>>#

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.

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. The default value is kDefaultLoadFactor.
Allocator – The Allocator to use. Must support rebind.

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.

using allocator_type = typename Base::allocator_type#: The Allocator.

Public Functions

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

inline explicit RHUnorderedMap( size_type reserved, const hasher &h = hasher(), const key_equal &ke = key_equal(), const allocator_type &al = allocator_type(), )#

Constructor with reservation hint.

Parameters:

reserved – Minimal number of slots to reserve on initialization.
h – Hash function to use.
ke – Comparison function to use for all key comparisons of this container.
al – Allocator to use for all memory allocations of this container.

inline RHUnorderedMap(size_type reserved, const allocator_type &al)#

Constructor with reservation hint and allocator.

Parameters:

reserved – Minimal number of slots to reserve on initialization.
al – Allocator to use for all memory allocations of this container.

inline RHUnorderedMap( size_type reserved, const hasher &h, const allocator_type &al, )#

Constructor with reservation hint, hash function and allocator.

Parameters:

reserved – Minimal number of slots to reserve on initialization.
h – Hash function to use.
al – Allocator to use for all memory allocations of this container.

inline explicit RHUnorderedMap(const allocator_type &al)#

Constructor with allocator.

Parameters:: al – Allocator to use for all memory allocations of this container.

template<class InputIt> inline RHUnorderedMap( InputIt first, InputIt last, size_type reserved = 0, const hasher &h = hasher(), const key_equal &ke = key_equal(), const allocator_type &al = allocator_type(), )#

Constructs the container with the contents of range [first, last).

Note

If multiple elements in the range [first, last) have equivalent keys, the first encountered key will be inserted.

Parameters:

first – The first iterator defining the source range of elements to copy.
last – The last iterator defining the source range of elements to copy.
reserved – A hint to the minimal number of slots to reserve.
h – Hash function to use.
ke – Comparison function to use for all key comparisons of this container.
al – Allocator to use for all memory allocations of this container.

template<class InputIt> inline RHUnorderedMap( InputIt first, InputIt last, size_type reserved, const allocator_type &al, )#

Constructs the container with the contents of range [first, last).

Note

If multiple elements in the range [first, last) have equivalent keys, the first encountered key will be inserted.

Parameters:

first – The first iterator defining the source range of elements to copy.
last – The last iterator defining the source range of elements to copy.
reserved – A hint to the minimal number of slots to reserve.
al – Allocator to use for all memory allocations of this container.

template<class InputIt> inline RHUnorderedMap( InputIt first, InputIt last, size_type reserved, const hasher &h, const allocator_type &al, )#

Constructs the container with the contents of range [first, last).

Note

If multiple elements in the range [first, last) have equivalent keys, the first encountered key will be inserted.

Parameters:

first – The first iterator defining the source range of elements to copy.
last – The last iterator defining the source range of elements to copy.
reserved – A hint to the minimal number of slots to reserve.
h – Hash function to use.
al – Allocator to use for all memory allocations of this container.

inline RHUnorderedMap( std::initializer_list<value_type> init, size_type reserved = 0, const hasher &h = hasher(), const key_equal &ke = key_equal(), const allocator_type &al = allocator_type(), )#

Constructs the container with the contents of items from an initializer_list.

Note

If multiple elements in init have equivalent keys, the first encountered key will be inserted.

Parameters:

init – initializer list to initialize the elements of the container with.
reserved – A hint to the minimal number of slots to reserve. If not specified, init.size() is used.
h – Hash function to use.
ke – Comparison function to use for all key comparisons of this container.
al – Allocator to use for all memory allocations of this container.

inline RHUnorderedMap( std::initializer_list<value_type> init, size_type reserved, const allocator_type &al, )#

Constructs the container with the contents of items from an initializer_list.

Note

If multiple elements in init have equivalent keys, the first encountered key will be inserted.

Parameters:

init – initializer list to initialize the elements of the container with.
reserved – A hint to the minimal number of slots to reserve.
al – Allocator to use for all memory allocations of this container.

inline RHUnorderedMap( std::initializer_list<value_type> init, size_type reserved, const hasher &h, const allocator_type &al, )#

Constructs the container with the contents of items from an initializer_list.

Note

If multiple elements in init have equivalent keys, the first encountered key will be inserted.

Parameters:

init – initializer list to initialize the elements of the container with.
reserved – A hint to the minimal number of slots to reserve.
h – Hash function to use.
al – Allocator to use for all memory allocations of this container.

inline RHUnorderedMap(const RHUnorderedMap &other)#

Copy constructor.

Copies elements from another container.

Complexity: Linear in size of other.

Note

*this may have a different capacity() than other.

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

inline RHUnorderedMap( const RHUnorderedMap &other, const Allocator &alloc, )#

Copy constructor with Allocator.

Copies elements from another container.

Complexity: Linear in size of other.

Note

*this may have a different capacity() than other.

Parameters:

other – The other container to copy entries from.
alloc – The allocator to use for all memory allocations of this container.

inline RHUnorderedMap(RHUnorderedMap &&other)#

Move constructor.

Moves elements from another container.

Complexity: Constant.

Note

No move constructors on contained elements are invoked. other will be empty() after this operation.

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

inline RHUnorderedMap( RHUnorderedMap &&other, const Allocator &alloc, )#

Move constructor with Allocator.

Moves elements from another container.

Complexity: Constant. If alloc is not equal to other.get_allocator(), then linear.

Note

No move constructors on contained elements are invoked. other will be empty() after this operation.

Parameters:

other – The other container to move entries from.
alloc – The Allocator to use for all memory allocations of this container.

~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<typename 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<typename ...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<typename ...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)...}.

If this function performs an insert, all iterators, references and pointers are invalidated.

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<typename ...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)...}.

If this function performs an insert, all iterators, references and pointers are invalidated.

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<typename K, typename ...Args, typename = std::enable_if_t<IsTransparent_v<K>>> inline std::pair<iterator, bool> try_emplace( K &&key, Args&&... args, )#

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

If a key equivalent to key already exists in the container, does nothing. Otherwise, inserts a new element into the container with key key and value constructed with args. In such case, behaves like emplace except that the element is constructed as

value_type(std::piecewise_construct,
           std::forward_as_tuple(std::forward<K>(key),
           std::forward_as_tuple(std::forward<Args>(args)...)));

If value_type is not EmplaceConstructible from the corresponding expression, the behavior is undefined.

If this function performs an insert, all iterators, references and pointers are invalidated.

Note

This overload participates in overload resolution only if Hash and KeyEqual are both transparent. This assumes that such Hash is callable with both K and Key type and that KeyEqual is transparent, which, together, allows calling this function without constructing an instance of Key.

inline size_type erase(const key_type &key)#

Removes elements with the given key.

References, pointers and iterators to the erased 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).

template<typename K, typename = std::enable_if_t<IsTransparent_v<K> && !std::is_convertible_v<K, const_iterator> && !std::is_convertible_v<K, const_find_iterator>>> inline size_type erase( const K &key, )#

Removes specified elements from the container.

Removes all elements with key that compares equivalent to the value key.

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

Note

This overload participates in overload resolution only if Hash and KeyEqual are both transparent. This assumes that such Hash is callable with both K and Key type and that KeyEqual is transparent, which, together, allows calling this function without constructing an instance of Key.

Parameters:: key – A value of any type that can be transparently compared with a key denoting the elements to remove.
Returns:: Number of elements removed.

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.

template<typename K, typename = std::enable_if_t<IsTransparent_v<K>>> inline mapped_type &at( const K &key, )#

Access specified element with bounds checking.

This function is only available if exceptions are enabled. Returns a reference to the mapped value of the element with the specified key. If no such element exists, an exception of type std::out_of_range is thrown. The key compares equivalent to the value key. The reference to the mapped value is obtained as if by expression this->find(key)->second. The expression this->find(key) must be well-formed and have well-defined behavior, otherwise the behavior is undefined.

Complexity: Average case: constant; worst case: linear in capacity().

Note

This overload participates in overload resolution only if Hash and KeyEqual are both transparent. This assumes that such Hash is callable with both K and Key type and that KeyEqual is transparent, which, together, allows calling this function without constructing an instance of Key.

Parameters:: key – A value of any type that can be transparently compared with a key.
Returns:: A reference to the mapped value of the requested element.

template<typename K, typename = std::enable_if_t<IsTransparent_v<K>>> inline const mapped_type &at( const K &key, ) const#

Access specified element with bounds checking.

This function is only available if exceptions are enabled. Returns a reference to the mapped value of the element with the specified key. If no such element exists, an exception of type std::out_of_range is thrown. The key compares equivalent to the value key. The reference to the mapped value is obtained as if by expression this->find(key)->second. The expression this->find(key) must be well-formed and have well-defined behavior, otherwise the behavior is undefined.

Complexity: Average case: constant; worst case: linear in capacity().

Note

This overload participates in overload resolution only if Hash and KeyEqual are both transparent. This assumes that such Hash is callable with both K and Key type and that KeyEqual is transparent, which, together, allows calling this function without constructing an instance of Key.

Parameters:: key – A value of any type that can be transparently compared with a key.
Returns:: A reference to the mapped value of the requested element.

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.

template<typename K, typename = std::enable_if_t<IsTransparent_v<K>>> inline mapped_type &operator[]( K &&key, )#

Access or insert specified element.

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

Inserts a value_type object constructed in-place if there is no key that transparently compares equivalent to the value key.

Equivalent to return this->try_emplace(std::forward<K>(key)).first->second;.

Complexity: Average case: constant; worst case: linear in capacity().

Note

This overload participates in overload resolution only if Hash and KeyEqual are both transparent. This assumes that such Hash is callable with both K and Key type and that KeyEqual is transparent, which, together, allows calling this function without constructing an instance of Key.

Parameters:: key – A value of any type that can be transparently compared with a key.
Returns:: A reference to the mapped valued of the new element if no element with a key that compares equivalent to the value key existed. Otherwise, a reference to the mapped value of the existing element whose key compares equivalent to key.

inline size_type 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).

template<typename K, typename = std::enable_if_t<IsTransparent_v<K>>> inline size_type count( const K &key, ) const#

Returns the number of elements matching the specified key.

Returns the number of elements with key that compares equivalent to the specified argument key.

Note

This overload participates in overload resolution only if Hash and KeyEqual are both transparent. This assumes that such Hash is callable with both K and Key type and that KeyEqual is transparent, which, together, allows calling this function without constructing an instance of Key.

Parameters:: key – A value of any type that can be transparently compared with a key.
Returns:: Number of elements with key that compares equivalent to key.

Public Static Attributes

static constexpr size_t LoadFactor = Base::LoadFactor#: The container’s LoadFactor.