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 348 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 370 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 422 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 426 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 427 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 376 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 374 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 372 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 367 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 423 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 352 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 368 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 375 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 369 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 364 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 373 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 371 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 366 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 365 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

Definition at line 530 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 558 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 573 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 893 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 906 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 899 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 912 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 640 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 631 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 997 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 1076 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 642 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 655 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 671 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 1290 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 1072 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 962 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 967 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 928 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 933 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 1061 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 1395 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 742 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 747 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 662 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 653 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 651 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 972 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 983 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 977 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 988 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 856 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 861 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 792 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 790 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 775 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 767 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 1130 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 942 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 952 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 947 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 957 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 1104 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 1110 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 624 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 1044 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 1067 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 700 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 685 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 690 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 1162 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 730 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 720 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 1211 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 1217 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 1230 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 1301 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 1046 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 1007 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 999 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 1017 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 1024 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 666 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 1015 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 1019 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 1051 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 1087 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 1096 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 594 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 617 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 923 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 1031 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 1264 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 1329 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 1037 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 1056 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 1353 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 664 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 1540 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 871 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 752 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 759 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 407 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 1513 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 1515 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 1519 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 1564 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 1558 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 1547 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 1573 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 1568 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 1571 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 1570 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 1566 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 1582 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 1517 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 1521 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 1516 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 1520 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 1534 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 384 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 399 of file robin_hash.h.

---

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

• robin_hash.h