tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > Class Template Reference

#include <robin_hash.h>

Inheritance diagram for tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >:

Classes
class	robin_iterator

Public Types
using	allocator_type = Allocator
using	const_iterator = robin_iterator< true >
using	const_pointer = const value_type *
using	const_reference = const value_type &
using	difference_type = std::ptrdiff_t
using	hasher = Hash
using	iterator = robin_iterator< false >
using	key_equal = KeyEqual
using	key_type = typename KeySelect::key_type
using	pointer = value_type *
using	reference = value_type &
using	size_type = std::size_t
using	value_type = ValueType

Public Member Functions
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>
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>
U::value_type &	at (const K &key, std::size_t 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, std::size_t hash) const
const_iterator	begin () const noexcept
iterator	begin () noexcept
size_type	bucket_count () const
const_iterator	cbegin () const noexcept
const_iterator	cend () const noexcept
void	clear () noexcept
template<class K >
bool	contains (const K &key) const
template<class K >
bool	contains (const K &key, std::size_t hash) const
template<class K >
size_type	count (const K &key) const
template<class K >
size_type	count (const K &key, std::size_t hash) const
template<class Deserializer >
void	deserialize (Deserializer &deserializer, bool hash_compatible)
template<class... Args>
std::pair< iterator, bool >	emplace (Args &&... args)
template<class... Args>
iterator	emplace_hint (const_iterator hint, Args &&... args)
bool	empty () const noexcept
const_iterator	end () const noexcept
iterator	end () noexcept
template<class K >
std::pair< iterator, iterator >	equal_range (const K &key)
template<class K >
std::pair< const_iterator, const_iterator >	equal_range (const K &key) const
template<class K >
std::pair< iterator, iterator >	equal_range (const K &key, std::size_t hash)
template<class K >
std::pair< const_iterator, const_iterator >	equal_range (const K &key, std::size_t hash) const
template<class K >
size_type	erase (const K &key)
template<class K >
size_type	erase (const K &key, std::size_t hash)
iterator	erase (const_iterator first, const_iterator last)
iterator	erase (const_iterator pos)
iterator	erase (iterator pos)
void	erase_fast (iterator pos)
template<class K >
iterator	find (const K &key)
template<class K >
const_iterator	find (const K &key) const
template<class K >
iterator	find (const K &key, std::size_t hash)
template<class K >
const_iterator	find (const K &key, std::size_t hash) const
allocator_type	get_allocator () const
hasher	hash_function () const
template<class InputIt >
void	insert (InputIt first, InputIt last)
template<typename P >
std::pair< iterator, bool >	insert (P &&value)
template<typename P >
iterator	insert_hint (const_iterator hint, P &&value)
template<class K , class M >
iterator	insert_or_assign (const_iterator hint, K &&key, M &&obj)
template<class K , class M >
std::pair< iterator, bool >	insert_or_assign (K &&key, M &&obj)
key_equal	key_eq () const
float	load_factor () const
size_type	max_bucket_count () const
float	max_load_factor () const
void	max_load_factor (float ml)
size_type	max_size () const noexcept
float	min_load_factor () const
void	min_load_factor (float ml)
iterator	mutable_iterator (const_iterator pos)
robin_hash &	operator= (const robin_hash &other)
robin_hash &	operator= (robin_hash &&other)
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type &	operator[] (K &&key)
void	rehash (size_type count_)
void	reserve (size_type count_)
	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 (size_type bucket_count, const Hash &hash, const KeyEqual &equal, const Allocator &alloc, float min_load_factor=DEFAULT_MIN_LOAD_FACTOR, float max_load_factor=DEFAULT_MAX_LOAD_FACTOR)
template<class Serializer >
void	serialize (Serializer &serializer) const
size_type	size () const noexcept
void	swap (robin_hash &other)
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)

Static Public Attributes
static const size_type	DEFAULT_INIT_BUCKETS_SIZE = 0
static constexpr float	DEFAULT_MAX_LOAD_FACTOR = 0.5f
static constexpr float	DEFAULT_MIN_LOAD_FACTOR = 0.0f
static constexpr float	MAXIMUM_MAX_LOAD_FACTOR = 0.95f
static constexpr float	MAXIMUM_MIN_LOAD_FACTOR = 0.15f
static constexpr float	MINIMUM_MAX_LOAD_FACTOR = 0.2f
static constexpr float	MINIMUM_MIN_LOAD_FACTOR = 0.0f

Private Types
using	bucket_entry = tsl::detail_robin_hash::bucket_entry< value_type, STORE_HASH >
using	buckets_allocator = typename std::allocator_traits< allocator_type >::template rebind_alloc< bucket_entry >
using	buckets_container_type = std::vector< bucket_entry, buckets_allocator >
using	distance_type = typename bucket_entry::distance_type
template<typename U >
using	has_mapped_type = typename std::integral_constant< bool, !std::is_same< U, void >::value >

Private Member Functions
std::size_t	bucket_for_hash (std::size_t hash) const
void	clear_and_shrink () noexcept
template<class K1 , class K2 >
bool	compare_keys (const K1 &key1, const K2 &key2) const
template<class Deserializer >
void	deserialize_impl (Deserializer &deserializer, bool hash_compatible)
void	erase_from_bucket (iterator pos)
template<class K >
iterator	find_impl (const K &key, std::size_t hash)
template<class K >
const_iterator	find_impl (const K &key, std::size_t hash) const
template<class K >
std::size_t	hash_key (const K &key) const
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 hash, Args &&... value_type_args)
void	insert_value (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type hash, value_type &&value)
void	insert_value_impl (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type hash, value_type &value)
void	insert_value_on_rehash (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type hash, value_type &&value)
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
void	rehash_impl (size_type count_)
bool	rehash_on_extreme_load (distance_type curr_dist_from_ideal_bucket)
template<class Serializer >
void	serialize_impl (Serializer &serializer) const
bucket_entry *	static_empty_bucket_ptr () noexcept

Static Private Member Functions
static bool	USE_STORED_HASH_ON_REHASH (size_type bucket_count)

Private Attributes
size_type	m_bucket_count
bucket_entry *	m_buckets
buckets_container_type	m_buckets_data
bool	m_grow_on_next_insert
size_type	m_load_threshold
float	m_max_load_factor
float	m_min_load_factor
size_type	m_nb_elements
bool	m_try_shrink_on_next_insert

Static Private Attributes
static const slz_size_type	SERIALIZATION_PROTOCOL_VERSION = 1
static constexpr bool	STORE_HASH
static constexpr bool	USE_STORED_HASH_ON_LOOKUP = StoreHash

Detailed Description

template<class ValueType, class KeySelect, class ValueSelect, class Hash, class KeyEqual, class Allocator, bool StoreHash, class GrowthPolicy>
class tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >

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.

Definition at line 362 of file robin_hash.h.

Member Typedef Documentation

allocator_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::allocator_type = Allocator

Definition at line 384 of file robin_hash.h.

bucket_entry

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::bucket_entry = tsl::detail_robin_hash::bucket_entry<value_type, STORE_HASH>

private

Definition at line 436 of file robin_hash.h.

buckets_allocator

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::buckets_allocator = typename std::allocator_traits< allocator_type>::template rebind_alloc<bucket_entry>

private

Definition at line 440 of file robin_hash.h.

buckets_container_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::buckets_container_type = std::vector<bucket_entry, buckets_allocator>

private

Definition at line 441 of file robin_hash.h.

const_iterator

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_iterator = robin_iterator<true>

Definition at line 390 of file robin_hash.h.

const_pointer

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_pointer = const value_type*

Definition at line 388 of file robin_hash.h.

const_reference

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_reference = const value_type&

Definition at line 386 of file robin_hash.h.

difference_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::difference_type = std::ptrdiff_t

Definition at line 381 of file robin_hash.h.

distance_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::distance_type = typename bucket_entry::distance_type

private

Definition at line 437 of file robin_hash.h.

has_mapped_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<typename U >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>

private

Definition at line 366 of file robin_hash.h.

hasher

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hasher = Hash

Definition at line 382 of file robin_hash.h.

iterator

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::iterator = robin_iterator<false>

Definition at line 389 of file robin_hash.h.

key_equal

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal = KeyEqual

Definition at line 383 of file robin_hash.h.

key_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_type = typename KeySelect::key_type

Definition at line 378 of file robin_hash.h.

pointer

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::pointer = value_type*

Definition at line 387 of file robin_hash.h.

reference

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reference = value_type&

Definition at line 385 of file robin_hash.h.

size_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::size_type = std::size_t

Definition at line 380 of file robin_hash.h.

value_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

using tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::value_type = ValueType

Definition at line 379 of file robin_hash.h.

Constructor & Destructor Documentation

robin_hash() [1/3]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::robin_hash ( size_type  bucket_count, const Hash &  hash, const KeyEqual &  equal, const Allocator &  alloc, float  min_load_factor = DEFAULT_MIN_LOAD_FACTOR, float  max_load_factor = DEFAULT_MAX_LOAD_FACTOR  )

inline

C++11 doesn't support the creation of a std::vector with a custom allocator and 'count' default-inserted elements. The needed contructor 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.

Definition at line 583 of file robin_hash.h.

robin_hash() [2/3]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::robin_hash ( const robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &  other )

inline

Definition at line 614 of file robin_hash.h.

robin_hash() [3/3]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::robin_hash ( robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &&  other )

inlinenoexcept

Definition at line 629 of file robin_hash.h.

Member Function Documentation

at() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>

U::value_type& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::at ( const K &  key )

inline

Definition at line 949 of file robin_hash.h.

at() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>

const U::value_type& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::at ( const K &  key ) const

inline

Definition at line 962 of file robin_hash.h.

at() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>

U::value_type& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::at ( const K &  key, std::size_t  hash  )

inline

Definition at line 955 of file robin_hash.h.

at() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>

const U::value_type& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::at ( const K &  key, std::size_t  hash  ) const

inline

Definition at line 968 of file robin_hash.h.

begin() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::begin ( ) const

inlinenoexcept

Definition at line 696 of file robin_hash.h.

begin() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::begin ( )

inlinenoexcept

Definition at line 687 of file robin_hash.h.

bucket_count()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::bucket_count ( ) const

inline

Definition at line 1053 of file robin_hash.h.

bucket_for_hash()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

std::size_t tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::bucket_for_hash ( std::size_t  hash ) const

inlineprivate

Definition at line 1132 of file robin_hash.h.

cbegin()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::cbegin ( ) const

inlinenoexcept

Definition at line 698 of file robin_hash.h.

cend()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::cend ( ) const

inlinenoexcept

Definition at line 711 of file robin_hash.h.

clear()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::clear ( )

inlinenoexcept

Definition at line 727 of file robin_hash.h.

clear_and_shrink()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::clear_and_shrink ( )

inlineprivatenoexcept

Definition at line 1346 of file robin_hash.h.

compare_keys()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K1 , class K2 >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::compare_keys ( const K1 &  key1, const K2 &  key2  ) const

inlineprivate

Definition at line 1128 of file robin_hash.h.

contains() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::contains ( const K &  key ) const

inline

Definition at line 1018 of file robin_hash.h.

contains() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::contains ( const K &  key, std::size_t  hash  ) const

inline

Definition at line 1023 of file robin_hash.h.

count() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::count ( const K &  key ) const

inline

Definition at line 984 of file robin_hash.h.

count() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::count ( const K &  key, std::size_t  hash  ) const

inline

Definition at line 989 of file robin_hash.h.

deserialize()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class Deserializer >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::deserialize ( Deserializer &  deserializer, bool  hash_compatible  )

inline

Definition at line 1117 of file robin_hash.h.

deserialize_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class Deserializer >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::deserialize_impl ( Deserializer &  deserializer, bool  hash_compatible  )

inlineprivate

Definition at line 1451 of file robin_hash.h.

emplace()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class... Args>

std::pair<iterator, bool> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::emplace ( Args &&...  args )

inline

Definition at line 798 of file robin_hash.h.

emplace_hint()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class... Args>

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::emplace_hint ( const_iterator  hint, Args &&...  args  )

inline

Definition at line 803 of file robin_hash.h.

empty()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::empty ( ) const

inlinenoexcept

Definition at line 718 of file robin_hash.h.

end() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::end ( ) const

inlinenoexcept

Definition at line 709 of file robin_hash.h.

end() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::end ( )

inlinenoexcept

Definition at line 707 of file robin_hash.h.

equal_range() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

std::pair<iterator, iterator> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::equal_range ( const K &  key )

inline

Definition at line 1028 of file robin_hash.h.

equal_range() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

std::pair<const_iterator, const_iterator> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::equal_range ( const K &  key ) const

inline

Definition at line 1039 of file robin_hash.h.

equal_range() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

std::pair<iterator, iterator> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::equal_range ( const K &  key, std::size_t  hash  )

inline

Definition at line 1033 of file robin_hash.h.

equal_range() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

std::pair<const_iterator, const_iterator> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::equal_range ( const K &  key, std::size_t  hash  ) const

inline

Definition at line 1044 of file robin_hash.h.

erase() [1/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase ( const K &  key )

inline

Definition at line 912 of file robin_hash.h.

erase() [2/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase ( const K &  key, std::size_t  hash  )

inline

Definition at line 917 of file robin_hash.h.

erase() [3/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase ( const_iterator  first, const_iterator  last  )

inline

Definition at line 848 of file robin_hash.h.

erase() [4/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase ( const_iterator  pos )

inline

Definition at line 846 of file robin_hash.h.

erase() [5/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase ( iterator  pos )

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.

Definition at line 831 of file robin_hash.h.

erase_fast()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase_fast ( iterator  pos )

inline

Definition at line 823 of file robin_hash.h.

erase_from_bucket()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::erase_from_bucket ( iterator  pos )

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.

Definition at line 1186 of file robin_hash.h.

find() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::find ( const K &  key )

inline

Definition at line 998 of file robin_hash.h.

find() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::find ( const K &  key ) const

inline

Definition at line 1008 of file robin_hash.h.

find() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::find ( const K &  key, std::size_t  hash  )

inline

Definition at line 1003 of file robin_hash.h.

find() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::find ( const K &  key, std::size_t  hash  ) const

inline

Definition at line 1013 of file robin_hash.h.

find_impl() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::find_impl ( const K &  key, std::size_t  hash  )

inlineprivate

Definition at line 1160 of file robin_hash.h.

find_impl() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

const_iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::find_impl ( const K &  key, std::size_t  hash  ) const

inlineprivate

Definition at line 1166 of file robin_hash.h.

get_allocator()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

allocator_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::get_allocator ( ) const

inline

Definition at line 680 of file robin_hash.h.

hash_function()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

hasher tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hash_function ( ) const

inline

Definition at line 1100 of file robin_hash.h.

hash_key()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K >

std::size_t tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hash_key ( const K &  key ) const

inlineprivate

Definition at line 1123 of file robin_hash.h.

insert() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class InputIt >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert ( InputIt  first, InputIt  last  )

inline

Definition at line 756 of file robin_hash.h.

insert() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<typename P >

std::pair<iterator, bool> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert ( P &&  value )

inline

Definition at line 741 of file robin_hash.h.

insert_hint()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<typename P >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_hint ( const_iterator  hint, P &&  value  )

inline

Definition at line 746 of file robin_hash.h.

insert_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class... Args>

std::pair<iterator, bool> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_impl ( const K &  key, Args &&...  value_type_args  )

inlineprivate

Definition at line 1218 of file robin_hash.h.

insert_or_assign() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class M >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_or_assign ( const_iterator  hint, K &&  key, M &&  obj  )

inline

Definition at line 786 of file robin_hash.h.

insert_or_assign() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class M >

std::pair<iterator, bool> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_or_assign ( K &&  key, M &&  obj  )

inline

Definition at line 776 of file robin_hash.h.

insert_value() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class... Args>

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_value ( std::size_t  ibucket, distance_type  dist_from_ideal_bucket, truncated_hash_type  hash, Args &&...  value_type_args  )

inlineprivate

Definition at line 1267 of file robin_hash.h.

insert_value() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_value ( std::size_t  ibucket, distance_type  dist_from_ideal_bucket, truncated_hash_type  hash, value_type &&  value  )

inlineprivate

Definition at line 1273 of file robin_hash.h.

insert_value_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_value_impl ( std::size_t  ibucket, distance_type  dist_from_ideal_bucket, truncated_hash_type  hash, value_type &  value  )

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.

Definition at line 1286 of file robin_hash.h.

insert_value_on_rehash()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::insert_value_on_rehash ( std::size_t  ibucket, distance_type  dist_from_ideal_bucket, truncated_hash_type  hash, value_type &&  value  )

inlineprivate

Definition at line 1357 of file robin_hash.h.

key_eq()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

key_equal tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_eq ( ) const

inline

Definition at line 1102 of file robin_hash.h.

load_factor()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::load_factor ( ) const

inline

Definition at line 1063 of file robin_hash.h.

max_bucket_count()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::max_bucket_count ( ) const

inline

Definition at line 1055 of file robin_hash.h.

max_load_factor() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::max_load_factor ( ) const

inline

Definition at line 1073 of file robin_hash.h.

max_load_factor() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::max_load_factor ( float  ml )

inline

Definition at line 1080 of file robin_hash.h.

max_size()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::max_size ( ) const

inlinenoexcept

Definition at line 722 of file robin_hash.h.

min_load_factor() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::min_load_factor ( ) const

inline

Definition at line 1071 of file robin_hash.h.

min_load_factor() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::min_load_factor ( float  ml )

inline

Definition at line 1075 of file robin_hash.h.

mutable_iterator()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::mutable_iterator ( const_iterator  pos )

inline

Definition at line 1107 of file robin_hash.h.

next_bucket() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class U = GrowthPolicy, typename std::enable_if< is_power_of_two_policy< U >::value >::type * = nullptr>

std::size_t tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::next_bucket ( std::size_t  index ) const

inlineprivatenoexcept

Definition at line 1143 of file robin_hash.h.

next_bucket() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class U = GrowthPolicy, typename std::enable_if<!is_power_of_two_policy< U >::value >::type * = nullptr>

std::size_t tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::next_bucket ( std::size_t  index ) const

inlineprivatenoexcept

Definition at line 1152 of file robin_hash.h.

operator=() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

robin_hash& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::operator= ( const robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &  other )

inline

Definition at line 650 of file robin_hash.h.

operator=() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

robin_hash& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::operator= ( robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &&  other )

inline

Definition at line 673 of file robin_hash.h.

operator[]()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>

U::value_type& tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::operator[] ( K &&  key )

inline

Definition at line 979 of file robin_hash.h.

rehash()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::rehash ( size_type  count_ )

inline

Definition at line 1087 of file robin_hash.h.

rehash_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::rehash_impl ( size_type  count_ )

inlineprivate

Definition at line 1320 of file robin_hash.h.

rehash_on_extreme_load()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::rehash_on_extreme_load ( distance_type  curr_dist_from_ideal_bucket )

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.

Definition at line 1385 of file robin_hash.h.

reserve()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reserve ( size_type  count_ )

inline

Definition at line 1093 of file robin_hash.h.

serialize()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class Serializer >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::serialize ( Serializer &  serializer ) const

inline

Definition at line 1112 of file robin_hash.h.

serialize_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class Serializer >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::serialize_impl ( Serializer &  serializer ) const

inlineprivate

Definition at line 1409 of file robin_hash.h.

size()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::size ( ) const

inlinenoexcept

Definition at line 720 of file robin_hash.h.

static_empty_bucket_ptr()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

bucket_entry* tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::static_empty_bucket_ptr ( )

inlineprivatenoexcept

Return an always valid pointer to an static empty bucket_entry with last_bucket() == true.

Definition at line 1593 of file robin_hash.h.

swap()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

void tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::swap ( robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > &  other )

inline

Definition at line 927 of file robin_hash.h.

try_emplace()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class... Args>

std::pair<iterator, bool> tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::try_emplace ( K &&  key, Args &&...  args  )

inline

Definition at line 808 of file robin_hash.h.

try_emplace_hint()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

template<class K , class... Args>

iterator tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::try_emplace_hint ( const_iterator  hint, K &&  key, Args &&...  args  )

inline

Definition at line 815 of file robin_hash.h.

USE_STORED_HASH_ON_REHASH()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

static bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::USE_STORED_HASH_ON_REHASH ( size_type  bucket_count )

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.

Definition at line 421 of file robin_hash.h.

Member Data Documentation

DEFAULT_INIT_BUCKETS_SIZE

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

const size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::DEFAULT_INIT_BUCKETS_SIZE = 0

static

Definition at line 1566 of file robin_hash.h.

DEFAULT_MAX_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::DEFAULT_MAX_LOAD_FACTOR = 0.5f

staticconstexpr

Definition at line 1568 of file robin_hash.h.

DEFAULT_MIN_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::DEFAULT_MIN_LOAD_FACTOR = 0.0f

staticconstexpr

Definition at line 1572 of file robin_hash.h.

m_bucket_count

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_bucket_count

private

Used a lot in find, avoid the call to m_buckets_data.size() which is a bit slower.

Definition at line 1617 of file robin_hash.h.

m_buckets

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

bucket_entry* tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_buckets

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.

Definition at line 1611 of file robin_hash.h.

m_buckets_data

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

buckets_container_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_buckets_data

private

Definition at line 1600 of file robin_hash.h.

m_grow_on_next_insert

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_grow_on_next_insert

private

Definition at line 1626 of file robin_hash.h.

m_load_threshold

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_load_threshold

private

Definition at line 1621 of file robin_hash.h.

m_max_load_factor

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_max_load_factor

private

Definition at line 1624 of file robin_hash.h.

m_min_load_factor

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_min_load_factor

private

Definition at line 1623 of file robin_hash.h.

m_nb_elements

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_nb_elements

private

Definition at line 1619 of file robin_hash.h.

m_try_shrink_on_next_insert

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::m_try_shrink_on_next_insert

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.

Definition at line 1635 of file robin_hash.h.

MAXIMUM_MAX_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::MAXIMUM_MAX_LOAD_FACTOR = 0.95f

staticconstexpr

Definition at line 1570 of file robin_hash.h.

MAXIMUM_MIN_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::MAXIMUM_MIN_LOAD_FACTOR = 0.15f

staticconstexpr

Definition at line 1574 of file robin_hash.h.

MINIMUM_MAX_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::MINIMUM_MAX_LOAD_FACTOR = 0.2f

staticconstexpr

Definition at line 1569 of file robin_hash.h.

MINIMUM_MIN_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr float tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::MINIMUM_MIN_LOAD_FACTOR = 0.0f

staticconstexpr

Definition at line 1573 of file robin_hash.h.

SERIALIZATION_PROTOCOL_VERSION

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

const slz_size_type tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::SERIALIZATION_PROTOCOL_VERSION = 1

staticprivate

Protocol version currenlty used for serialization.

Definition at line 1587 of file robin_hash.h.

STORE_HASH

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::STORE_HASH

staticconstexprprivate

Initial value:

=
      StoreHash ||
      ((sizeof(tsl::detail_robin_hash::bucket_entry<value_type, true>) ==
        sizeof(tsl::detail_robin_hash::bucket_entry<value_type, false>)) &&
       (sizeof(std::size_t) == sizeof(truncated_hash_type) ||
        is_power_of_two_policy<GrowthPolicy>::value) &&
       
       (!std::is_arithmetic<key_type>::value ||
        !std::is_same<Hash, std::hash<key_type>>::value))

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.

Definition at line 398 of file robin_hash.h.

USE_STORED_HASH_ON_LOOKUP

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , bool StoreHash, class GrowthPolicy >

constexpr bool tsl::detail_robin_hash::robin_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::USE_STORED_HASH_ON_LOOKUP = StoreHash

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.

Definition at line 413 of file robin_hash.h.

---

The documentation for this class was generated from the following file:

• robin_hash.h