template class tsl::robin_map
Overview
Implementation of a hash map using open-addressing and the robin hood hashing algorithm with backward shift deletion.
For operations modifying the hash map (insert, erase, rehash, …), the strong exception guarantee is only guaranteed when the expression std::is_nothrow_swappable<std::pair<Key, T>>::value && std::is_nothrow_move_constructible<std::pair<Key, T>>::value is true, otherwise if an exception is thrown during the swap or the move, the hash map may end up in a undefined state. Per the standard a Key or T with a noexcept copy constructor and no move constructor also satisfies the std::is_nothrow_move_constructible<std::pair<Key, T>>::value criterion (and will thus guarantee the strong exception for the map).
When StoreHash is true, 32 bits of the hash are stored alongside the values. It can improve the performance during lookups if the KeyEqual function takes time (if it engenders a cache-miss for example) as we then compare the stored hashes before comparing the keys. When tsl::rh::power_of_two_growth_policy is used as GrowthPolicy, it may also speed-up the rehash process as we can avoid to recalculate the hash. When it is detected that storing the hash will not incur any memory penalty due to alignment (i.e. sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, true>) == sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)) and tsl::rh::power_of_two_growth_policy is used, the hash will be stored even if StoreHash is false so that we can speed-up the rehash (but it will not be used on lookups unless StoreHash is true).
GrowthPolicy defines how the map grows and consequently how a hash value is mapped to a bucket. By default the map uses tsl::rh::power_of_two_growth_policy. This policy keeps the number of buckets to a power of two and uses a mask to map the hash to a bucket instead of the slow modulo. Other growth policies are available and you may define your own growth policy, check tsl::rh::power_of_two_growth_policy for the interface.
std::pair<Key, T> must be swappable.
Key and T must be copy and/or move constructible.
If the destructor of Key or T throws an exception, the behaviour of the class is undefined.
Iterators invalidation:
clear, operator=, reserve, rehash: always invalidate the iterators.
insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the iterators.
erase: always invalidate the iterators.
#include <robin_map.h> template < class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<std::pair<Key, T>>, bool StoreHash = false, class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2> > class robin_map { public: // typedefs typedef typename ht::key_type key_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::size_type size_type; typedef typename ht::difference_type difference_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::allocator_type allocator_type; typedef typename ht::reference reference; typedef typename ht::const_reference const_reference; typedef typename ht::pointer pointer; typedef typename ht::const_pointer const_pointer; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; // classes class KeySelect; class ValueSelect; // construction robin_map(); robin_map( size_type bucket_count, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(), const Allocator& alloc = Allocator() ); robin_map( size_type bucket_count, const Allocator& alloc ); robin_map( size_type bucket_count, const Hash& hash, const Allocator& alloc ); robin_map(const Allocator& alloc); template <class InputIt> robin_map( InputIt first, InputIt last, size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(), const Allocator& alloc = Allocator() ); template <class InputIt> robin_map( InputIt first, InputIt last, size_type bucket_count, const Allocator& alloc ); template <class InputIt> robin_map( InputIt first, InputIt last, size_type bucket_count, const Hash& hash, const Allocator& alloc ); robin_map( std::initializer_list<value_type> init, size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(), const Allocator& alloc = Allocator() ); robin_map( std::initializer_list<value_type> init, size_type bucket_count, const Allocator& alloc ); robin_map( std::initializer_list<value_type> init, size_type bucket_count, const Hash& hash, const Allocator& alloc ); // methods robin_map& operator = (std::initializer_list<value_type> ilist); allocator_type get_allocator() const; iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; bool empty() const; size_type size() const; size_type max_size() const; void clear(); std::pair<iterator, bool> insert(const value_type& value); template < class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr > std::pair<iterator, bool> insert(P&& value); std::pair<iterator, bool> insert(value_type&& value); iterator insert( const_iterator hint, const value_type& value ); template < class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr > iterator insert( const_iterator hint, P&& value ); iterator insert( const_iterator hint, value_type&& value ); template <class InputIt> void insert( InputIt first, InputIt last ); void insert(std::initializer_list<value_type> ilist); template <class M> std::pair<iterator, bool> insert_or_assign( const key_type& k, M&& obj ); template <class M> std::pair<iterator, bool> insert_or_assign( key_type&& k, M&& obj ); template <class M> iterator insert_or_assign( const_iterator hint, const key_type& k, M&& obj ); template <class M> iterator insert_or_assign( const_iterator hint, key_type&& k, M&& obj ); template <class... Args> std::pair<iterator, bool> emplace(Args&&... args); template <class... Args> iterator emplace_hint(const_iterator hint, Args&&... args); template <class... Args> std::pair<iterator, bool> try_emplace( const key_type& k, Args&&... args ); template <class... Args> std::pair<iterator, bool> try_emplace( key_type&& k, Args&&... args ); template <class... Args> iterator try_emplace( const_iterator hint, const key_type& k, Args&&... args ); template <class... Args> iterator try_emplace( const_iterator hint, key_type&& k, Args&&... args ); iterator erase(iterator pos); iterator erase(const_iterator pos); iterator erase( const_iterator first, const_iterator last ); size_type erase(const key_type& key); size_type erase(const key_type& key, std::size_t precalculated_hash); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type erase(const K& key); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type erase( const K& key, std::size_t precalculated_hash ); void swap(robin_map& other); T& at(const Key& key); T& at(const Key& key, std::size_t precalculated_hash); const T& at(const Key& key) const; const T& at(const Key& key, std::size_t precalculated_hash) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > T& at(const K& key); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > T& at( const K& key, std::size_t precalculated_hash ); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const T& at(const K& key) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const T& at( const K& key, std::size_t precalculated_hash ) const; T& operator [] (const Key& key); T& operator [] (Key&& key); size_type count(const Key& key) const; size_type count(const Key& key, std::size_t precalculated_hash) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type count(const K& key) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type count( const K& key, std::size_t precalculated_hash ) const; iterator find(const Key& key); iterator find(const Key& key, std::size_t precalculated_hash); const_iterator find(const Key& key) const; const_iterator find(const Key& key, std::size_t precalculated_hash) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > iterator find(const K& key); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > iterator find( const K& key, std::size_t precalculated_hash ); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const_iterator find(const K& key) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const_iterator find( const K& key, std::size_t precalculated_hash ) const; bool contains(const Key& key) const; bool contains(const Key& key, std::size_t precalculated_hash) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > bool contains(const K& key) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > bool contains( const K& key, std::size_t precalculated_hash ) const; std::pair<iterator, iterator> equal_range(const Key& key); std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash); std::pair<const_iterator, const_iterator> equal_range(const Key& key) const; std::pair<const_iterator, const_iterator> equal_range(const Key& key, std::size_t precalculated_hash) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<iterator, iterator> equal_range(const K& key); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<iterator, iterator> equal_range( const K& key, std::size_t precalculated_hash ); template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<const_iterator, const_iterator> equal_range(const K& key) const; template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<const_iterator, const_iterator> equal_range( const K& key, std::size_t precalculated_hash ) const; size_type bucket_count() const; size_type max_bucket_count() const; float load_factor() const; float min_load_factor() const; float max_load_factor() const; void min_load_factor(float ml); void max_load_factor(float ml); void rehash(size_type count_); void reserve(size_type count_); hasher hash_function() const; key_equal key_eq() const; iterator mutable_iterator(const_iterator pos); template <class Serializer> void serialize(Serializer& serializer) const; template <class Deserializer> static robin_map deserialize( Deserializer& deserializer, bool hash_compatible = false ); };
Methods
template <class... Args> std::pair<iterator, bool> emplace(Args&&... args)
Due to the way elements are stored, emplace will need to move or copy the key-value once. The method is equivalent to insert(value_type(std::forward<Args>(args)…));
Mainly here for compatibility with the std::unordered_map interface.
template <class... Args> iterator emplace_hint(const_iterator hint, Args&&... args)
Due to the way elements are stored, emplace_hint will need to move or copy the key-value once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)…));
Mainly here for compatibility with the std::unordered_map interface.
size_type erase(const key_type& key, std::size_t precalculated_hash)
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup to the value if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type erase(const K& key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type erase( const K& key, std::size_t precalculated_hash )
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup to the value if you already have the hash.
T& at(const Key& key, std::size_t precalculated_hash)
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
const T& at(const Key& key, std::size_t precalculated_hash) const
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > T& at(const K& key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > T& at( const K& key, std::size_t precalculated_hash )
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const T& at(const K& key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const T& at( const K& key, std::size_t precalculated_hash ) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
size_type count(const Key& key, std::size_t precalculated_hash) const
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type count(const K& key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > size_type count( const K& key, std::size_t precalculated_hash ) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
iterator find(const Key& key, std::size_t precalculated_hash)
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
const_iterator find(const Key& key, std::size_t precalculated_hash) const
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > iterator find(const K& key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > iterator find( const K& key, std::size_t precalculated_hash )
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const_iterator find(const K& key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > const_iterator find( const K& key, std::size_t precalculated_hash ) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
bool contains(const Key& key, std::size_t precalculated_hash) const
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > bool contains(const K& key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > bool contains( const K& key, std::size_t precalculated_hash ) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash)
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
std::pair<const_iterator, const_iterator> equal_range(const Key& key, std::size_t precalculated_hash) const
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<iterator, iterator> equal_range(const K& key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<iterator, iterator> equal_range( const K& key, std::size_t precalculated_hash )
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<const_iterator, const_iterator> equal_range(const K& key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
template < class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr > std::pair<const_iterator, const_iterator> equal_range( const K& key, std::size_t precalculated_hash ) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
Use the hash value ‘precalculated_hash’ instead of hashing the key. The hash value should be the same as hash_function() (key). Useful to speed-up the lookup if you already have the hash.
void min_load_factor(float ml)
Set the min_load_factor to ml. When the load_factor of the map goes below min_load_factor after some erase operations, the map will be shrunk when an insertion occurs. The erase method itself never shrinks the map.
The default value of min_load_factor is 0.0f, the map never shrinks by default.
iterator mutable_iterator(const_iterator pos)
Convert a const_iterator to an iterator.
template <class Serializer> void serialize(Serializer& serializer) const
Serialize the map through the serializer parameter.
The serializer parameter must be a function object that supports the following call:
template<typename U> void operator()(const U& value);where the typesstd::int16_t,std::uint32_t,std::uint64_t,floatandstd::pair<Key, T>must be supported for U.
The implementation leaves binary compatibility (endianness, IEEE 754 for floats, …) of the types it serializes in the hands of the Serializer function object if compatibility is required.
template <class Deserializer> static robin_map deserialize( Deserializer& deserializer, bool hash_compatible = false )
Deserialize a previously serialized map through the deserializer parameter.
The deserializer parameter must be a function object that supports the following call:
template<typename U> U operator()();where the typesstd::int16_t,std::uint32_t,std::uint64_t,floatandstd::pair<Key, T>must be supported for U.
If the deserialized hash map type is hash compatible with the serialized map, the deserialization process can be sped up by setting hash_compatible to true. To be hash compatible, the Hash, KeyEqual and GrowthPolicy must behave the same way than the ones used on the serialized map and the StoreHash must have the same value. The std::size_t must also be of the same size as the one on the platform used to serialize the map. If these criteria are not met, the behaviour is undefined with hash_compatible sets to true.
The behaviour is undefined if the type Key and T of the robin_map are not the same as the types used during serialization.
The implementation leaves binary compatibility (endianness, IEEE 754 for floats, size of int, …) of the types it deserializes in the hands of the Deserializer function object if compatibility is required.