#include <robin_hash.h>
Classes | |
class | robin_iterator |
Public Types | |
using | key_type = typename KeySelect::key_type |
using | value_type = ValueType |
using | size_type = std::size_t |
using | difference_type = std::ptrdiff_t |
using | hasher = Hash |
using | key_equal = KeyEqual |
using | allocator_type = Allocator |
using | reference = value_type & |
using | const_reference = const value_type & |
using | pointer = value_type * |
using | const_pointer = const value_type * |
using | iterator = robin_iterator<false> |
using | const_iterator = robin_iterator<true> |
Public Member Functions | |
robin_hash (size_type bucket_count, const Hash &my_hash, const KeyEqual &equal, const Allocator &alloc, float min_load_factor=DEFAULT_MIN_LOAD_FACTOR, float max_load_factor=DEFAULT_MAX_LOAD_FACTOR) | |
robin_hash (const robin_hash &other) | |
robin_hash (robin_hash &&other) noexcept(std::is_nothrow_move_constructible< Hash >::value &&std::is_nothrow_move_constructible< KeyEqual >::value &&std::is_nothrow_move_constructible< GrowthPolicy >::value &&std::is_nothrow_move_constructible< buckets_container_type >::value) | |
robin_hash & | operator= (const robin_hash &other) |
robin_hash & | operator= (robin_hash &&other) |
allocator_type | get_allocator () const |
iterator | begin () noexcept |
const_iterator | begin () const noexcept |
const_iterator | cbegin () const noexcept |
iterator | end () noexcept |
const_iterator | end () const noexcept |
const_iterator | cend () const noexcept |
bool | empty () const noexcept |
size_type | size () const noexcept |
size_type | max_size () const noexcept |
void | clear () noexcept |
template<typename P > | |
std::pair< iterator, bool > | insert (P &&value) |
template<typename P > | |
iterator | insert_hint (const_iterator hint, P &&value) |
template<class InputIt > | |
void | insert (InputIt first, InputIt last) |
template<class K , class M > | |
std::pair< iterator, bool > | insert_or_assign (K &&key, M &&obj) |
template<class K , class M > | |
iterator | insert_or_assign (const_iterator hint, K &&key, 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 K , class... Args> | |
std::pair< iterator, bool > | try_emplace (K &&key, Args &&...args) |
template<class K , class... Args> | |
iterator | try_emplace_hint (const_iterator hint, K &&key, Args &&...args) |
iterator | erase (iterator pos) |
iterator | erase (const_iterator pos) |
iterator | erase (const_iterator first, const_iterator last) |
template<class K > | |
size_type | erase (const K &key) |
template<class K > | |
size_type | erase (const K &key, std::size_t my_hash) |
void | swap (robin_hash &other) |
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr> | |
U::value_type & | at (const K &key) |
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr> | |
U::value_type & | at (const K &key, std::size_t my_hash) |
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr> | |
const U::value_type & | at (const K &key) const |
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr> | |
const U::value_type & | at (const K &key, std::size_t my_hash) const |
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr> | |
U::value_type & | operator[] (K &&key) |
template<class K > | |
size_type | count (const K &key) const |
template<class K > | |
size_type | count (const K &key, std::size_t my_hash) const |
template<class K > | |
iterator | find (const K &key) |
template<class K > | |
iterator | find (const K &key, std::size_t my_hash) |
template<class K > | |
const_iterator | find (const K &key) const |
template<class K > | |
const_iterator | find (const K &key, std::size_t my_hash) const |
template<class K > | |
bool | contains (const K &key) const |
template<class K > | |
bool | contains (const K &key, std::size_t my_hash) const |
template<class K > | |
std::pair< iterator, iterator > | equal_range (const K &key) |
template<class K > | |
std::pair< iterator, iterator > | equal_range (const K &key, std::size_t my_hash) |
template<class K > | |
std::pair< const_iterator, const_iterator > | equal_range (const K &key) const |
template<class K > | |
std::pair< const_iterator, const_iterator > | equal_range (const K &key, std::size_t my_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 my_count) |
void | reserve (size_type my_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 > | |
void | deserialize (Deserializer &deserializer, bool hash_compatible) |
Static Public Attributes | |
static const size_type | DEFAULT_INIT_BUCKETS_SIZE = 0 |
static constexpr float | DEFAULT_MAX_LOAD_FACTOR = 0.5f |
static constexpr float | MINIMUM_MAX_LOAD_FACTOR = 0.2f |
static constexpr float | MAXIMUM_MAX_LOAD_FACTOR = 0.95f |
static constexpr float | DEFAULT_MIN_LOAD_FACTOR = 0.0f |
static constexpr float | MINIMUM_MIN_LOAD_FACTOR = 0.0f |
static constexpr float | MAXIMUM_MIN_LOAD_FACTOR = 0.15f |
Private Types | |
template<typename U > | |
using | has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value> |
using | bucket_entry = tsl::detail_robin_hash::bucket_entry<value_type, STORE_HASH> |
using | distance_type = typename bucket_entry::distance_type |
using | buckets_allocator |
using | buckets_container_type = std::vector<bucket_entry, buckets_allocator> |
Private Member Functions | |
template<class K > | |
std::size_t | hash_key (const K &key) const |
template<class K1 , class K2 > | |
bool | compare_keys (const K1 &key1, const K2 &key2) const |
std::size_t | bucket_for_hash (std::size_t my_hash) const |
template<class U = GrowthPolicy, typename std::enable_if< is_power_of_two_policy< U >::value >::type * = nullptr> | |
std::size_t | next_bucket (std::size_t index) const noexcept |
template<class U = GrowthPolicy, typename std::enable_if<!is_power_of_two_policy< U >::value >::type * = nullptr> | |
std::size_t | next_bucket (std::size_t index) const noexcept |
template<class K > | |
iterator | find_impl (const K &key, std::size_t my_hash) |
template<class K > | |
const_iterator | find_impl (const K &key, std::size_t my_hash) const |
void | erase_from_bucket (iterator pos) |
template<class K , class... Args> | |
std::pair< iterator, bool > | insert_impl (const K &key, Args &&...value_type_args) |
template<class... Args> | |
void | insert_value (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, Args &&...value_type_args) |
void | insert_value (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &&value) |
void | insert_value_impl (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &value) |
void | rehash_impl (size_type my_count) |
void | clear_and_shrink () noexcept |
void | insert_value_on_rehash (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &&value) |
bool | rehash_on_extreme_load (distance_type curr_dist_from_ideal_bucket) |
template<class Serializer > | |
void | serialize_impl (Serializer &serializer) const |
template<class Deserializer > | |
void | deserialize_impl (Deserializer &deserializer, bool hash_compatible) |
bucket_entry * | static_empty_bucket_ptr () noexcept |
Static Private Member Functions | |
static bool | USE_STORED_HASH_ON_REHASH (size_type bucket_count) |
Private Attributes | |
buckets_container_type | m_buckets_data |
bucket_entry * | m_buckets |
size_type | m_bucket_count |
size_type | m_nb_elements {0} |
size_type | m_load_threshold {0} |
float | m_min_load_factor |
float | m_max_load_factor |
bool | m_grow_on_next_insert {false} |
bool | m_try_shrink_on_next_insert {false} |
Static Private Attributes | |
static constexpr bool | STORE_HASH |
static constexpr bool | USE_STORED_HASH_ON_LOOKUP = StoreHash |
static const slz_size_type | SERIALIZATION_PROTOCOL_VERSION = 1 |
Internal common class used by robin_map
and robin_set
.
ValueType is what will be stored by robin_hash
(usually std::pair<Key, T>
for map and Key
for set).
KeySelect
should be a FunctionObject
which takes a ValueType
in parameter and returns a reference to the key.
ValueSelect
should be a FunctionObject
which takes a ValueType
in parameter and returns a reference to the value. ValueSelect
should be void if there is no value (in a set for example).
The strong exception guarantee only holds if the expression std::is_nothrow_swappable<ValueType>\:\:value && std::is_nothrow_move_constructible<ValueType>\:\:value
is true.
Behaviour is undefined if the destructor of ValueType
throws.
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::allocator_type = Allocator |
|
private |
|
private |
|
private |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_iterator = robin_iterator<true> |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_pointer = const value_type * |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_reference = const value_type & |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::difference_type = std::ptrdiff_t |
|
private |
|
private |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hasher = Hash |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::iterator = robin_iterator<false> |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal = KeyEqual |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_type = typename KeySelect::key_type |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::pointer = value_type * |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reference = value_type & |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::size_type = std::size_t |
using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::value_type = ValueType |
|
inline |
C++11 doesn't support the creation of a std::vector with a custom allocator and 'count' default-inserted elements. The needed constructor explicit vector(size_type count, const Allocator& alloc = Allocator());
is only available in C++14 and later. We thus must resize after using the vector(const Allocator& alloc)
constructor.
We can't use vector(size_type count, const T& value, const Allocator& alloc)
as it requires the value T to be copyable.
|
inline |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
|
inlineprivate |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlineprivatenoexcept |
|
inlineprivate |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlineprivate |
|
inline |
|
inline |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Here to avoid template<class K> size_type erase(const K& key)
being used when we use an iterator
instead of a const_iterator
.
Erase bucket used a backward shift after clearing the bucket. Check if there is a new value in the bucket, if not get the next non-empty.
|
inlineprivate |
Backward shift, swap the empty bucket, previous_ibucket, with the values on its right, ibucket, until we cross another empty bucket or if the other bucket has a distance_from_ideal_bucket == 0.
We try to move the values closer to their ideal bucket.
|
inline |
|
inline |
|
inline |
|
inline |
|
inlineprivate |
|
inlineprivate |
|
inline |
|
inline |
|
inlineprivate |
|
inline |
|
inline |
|
inline |
|
inlineprivate |
|
inline |
|
inline |
|
inlineprivate |
|
inlineprivate |
|
inlineprivate |
The number of probes is really high, rehash the map on the next insert. Difficult to do now as rehash may throw an exception.
|
inlineprivate |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
|
inlineprivatenoexcept |
|
inlineprivatenoexcept |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlineprivate |
|
inlineprivate |
Grow the table if m_grow_on_next_insert is true or we reached the max_load_factor. Shrink the table if m_try_shrink_on_next_insert is true (an erase occurred) and we're below the min_load_factor.
Return true if the table has been rehashed.
|
inline |
|
inline |
|
inlineprivate |
|
inlinenoexcept |
|
inlineprivatenoexcept |
Return an always valid pointer to an static empty bucket_entry with last_bucket() == true.
|
inline |
|
inline |
|
inline |
|
inlinestaticprivate |
We can only use the hash on rehash if the size of the hash type is the same as the stored one or if we use a power of two modulo. In the case of the power of two modulo, we just mask the least significant bytes, we just have to check that the truncated_hash_type didn't truncated more bytes.
|
static |
|
staticconstexpr |
|
staticconstexpr |
|
private |
Used a lot in find, avoid the call to m_buckets_data.size() which is a bit slower.
|
private |
Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points to static_empty_bucket_ptr. This variable is useful to avoid the cost of checking if m_buckets_data is empty when trying to find an element.
TODO Remove m_buckets_data and only use a pointer instead of a pointer+vector to save some space in the robin_hash object. Manage the Allocator manually.
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
We can't shrink down the map on erase operations as the erase methods need to return the next iterator. Shrinking the map would invalidate all the iterators and we could not return the next iterator in a meaningful way, On erase, we thus just indicate on erase that we should try to shrink the hash table on the next insert if we go below the min_load_factor.
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticprivate |
Protocol version currently used for serialization.
|
staticconstexprprivate |
Either store the hash because we are asked by the StoreHash
template parameter or store the hash because it doesn't cost us anything in size and can be used to speed up rehash.
|
staticconstexprprivate |
Only use the stored hash on lookup if we are explicitly asked. We are not sure how slow the KeyEqual operation is. An extra comparison may slow things down with a fast KeyEqual.