#include <robin_hash.h>

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

[legend]

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

[legend]

Classes
class	robin_iterator

Public Types
using	key_type = typename KeySelect::key_type

using	value_type = ValueType

using	size_type = std::size_t

using	difference_type = std::ptrdiff_t

using	hasher = Hash

using	key_equal = KeyEqual

using	allocator_type = Allocator

using	reference = value_type &

using	const_reference = const value_type &

using	pointer = value_type *

using	const_pointer = const value_type *

using	iterator = robin_iterator<false>

using	const_iterator = robin_iterator<true>

Public Member Functions
	robin_hash (size_type bucket_count, const Hash &my_hash, const KeyEqual &equal, const Allocator &alloc, float min_load_factor=DEFAULT_MIN_LOAD_FACTOR, float max_load_factor=DEFAULT_MAX_LOAD_FACTOR)

	robin_hash (const robin_hash &other)

	robin_hash (robin_hash &&other) noexcept(std::is_nothrow_move_constructible< Hash >::value &&std::is_nothrow_move_constructible< KeyEqual >::value &&std::is_nothrow_move_constructible< GrowthPolicy >::value &&std::is_nothrow_move_constructible< buckets_container_type >::value)

robin_hash &	operator= (const robin_hash &other)

robin_hash &	operator= (robin_hash &&other)

allocator_type	get_allocator () const

iterator	begin () noexcept

const_iterator	begin () const noexcept

const_iterator	cbegin () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

const_iterator	cend () const noexcept

bool	empty () const noexcept

size_type	size () const noexcept

size_type	max_size () const noexcept

void	clear () noexcept

template<typename P >
std::pair< iterator, bool >	insert (P &&value)

template<typename P >
iterator	insert_hint (const_iterator hint, P &&value)

template<class InputIt >
void	insert (InputIt first, InputIt last)

template<class K , class M >
std::pair< iterator, bool >	insert_or_assign (K &&key, M &&obj)

template<class K , class M >
iterator	insert_or_assign (const_iterator hint, K &&key, M &&obj)

template<class... Args>
std::pair< iterator, bool >	emplace (Args &&...args)

template<class... Args>
iterator	emplace_hint (const_iterator hint, Args &&...args)

template<class K , class... Args>
std::pair< iterator, bool >	try_emplace (K &&key, Args &&...args)

template<class K , class... Args>
iterator	try_emplace_hint (const_iterator hint, K &&key, Args &&...args)

iterator	erase (iterator pos)

iterator	erase (const_iterator pos)

iterator	erase (const_iterator first, const_iterator last)

template<class K >
size_type	erase (const K &key)

template<class K >
size_type	erase (const K &key, std::size_t my_hash)

void	swap (robin_hash &other)

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type &	at (const K &key)

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type &	at (const K &key, std::size_t my_hash)

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
const U::value_type &	at (const K &key) const

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
const U::value_type &	at (const K &key, std::size_t my_hash) const

template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type &	operator[] (K &&key)

template<class K >
size_type	count (const K &key) const

template<class K >
size_type	count (const K &key, std::size_t my_hash) const

template<class K >
iterator	find (const K &key)

template<class K >
iterator	find (const K &key, std::size_t my_hash)

template<class K >
const_iterator	find (const K &key) const

template<class K >
const_iterator	find (const K &key, std::size_t my_hash) const

template<class K >
bool	contains (const K &key) const

template<class K >
bool	contains (const K &key, std::size_t my_hash) const

template<class K >
std::pair< iterator, iterator >	equal_range (const K &key)

template<class K >
std::pair< iterator, iterator >	equal_range (const K &key, std::size_t my_hash)

template<class K >
std::pair< const_iterator, const_iterator >	equal_range (const K &key) const

template<class K >
std::pair< const_iterator, const_iterator >	equal_range (const K &key, std::size_t my_hash) const

size_type	bucket_count () const

size_type	max_bucket_count () const

float	load_factor () const

float	min_load_factor () const

float	max_load_factor () const

void	min_load_factor (float ml)

void	max_load_factor (float ml)

void	rehash (size_type my_count)

void	reserve (size_type my_count)

hasher	hash_function () const

key_equal	key_eq () const

iterator	mutable_iterator (const_iterator pos)

template<class Serializer >
void	serialize (Serializer &serializer) const

template<class Deserializer >
void	deserialize (Deserializer &deserializer, bool hash_compatible)

Static Public Attributes
static const size_type	DEFAULT_INIT_BUCKETS_SIZE = 0

static constexpr float	DEFAULT_MAX_LOAD_FACTOR = 0.5f

static constexpr float	MINIMUM_MAX_LOAD_FACTOR = 0.2f

static constexpr float	MAXIMUM_MAX_LOAD_FACTOR = 0.95f

static constexpr float	DEFAULT_MIN_LOAD_FACTOR = 0.0f

static constexpr float	MINIMUM_MIN_LOAD_FACTOR = 0.0f

static constexpr float	MAXIMUM_MIN_LOAD_FACTOR = 0.15f

Private Types
template<typename U >
using	has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>

using	bucket_entry = tsl::detail_robin_hash::bucket_entry<value_type, STORE_HASH>

using	distance_type = typename bucket_entry::distance_type

using	buckets_allocator

using	buckets_container_type = std::vector<bucket_entry, buckets_allocator>

Private Member Functions
template<class K >
std::size_t	hash_key (const K &key) const

template<class K1 , class K2 >
bool	compare_keys (const K1 &key1, const K2 &key2) const

std::size_t	bucket_for_hash (std::size_t my_hash) const

template<class U = GrowthPolicy, typename std::enable_if< is_power_of_two_policy< U >::value >::type * = nullptr>
std::size_t	next_bucket (std::size_t index) const noexcept

template<class U = GrowthPolicy, typename std::enable_if<!is_power_of_two_policy< U >::value >::type * = nullptr>
std::size_t	next_bucket (std::size_t index) const noexcept

template<class K >
iterator	find_impl (const K &key, std::size_t my_hash)

template<class K >
const_iterator	find_impl (const K &key, std::size_t my_hash) const

void	erase_from_bucket (iterator pos)

template<class K , class... Args>
std::pair< iterator, bool >	insert_impl (const K &key, Args &&...value_type_args)

template<class... Args>
void	insert_value (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, Args &&...value_type_args)

void	insert_value (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &&value)

void	insert_value_impl (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &value)

void	rehash_impl (size_type my_count)

void	clear_and_shrink () noexcept

void	insert_value_on_rehash (std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &&value)

bool	rehash_on_extreme_load (distance_type curr_dist_from_ideal_bucket)

template<class Serializer >
void	serialize_impl (Serializer &serializer) const

template<class Deserializer >
void	deserialize_impl (Deserializer &deserializer, bool hash_compatible)

bucket_entry *	static_empty_bucket_ptr () noexcept

Static Private Member Functions
static bool	USE_STORED_HASH_ON_REHASH (size_type bucket_count)

Private Attributes
buckets_container_type	m_buckets_data

bucket_entry *	m_buckets

size_type	m_bucket_count

size_type	m_nb_elements {0}

size_type	m_load_threshold {0}

float	m_min_load_factor

float	m_max_load_factor

bool	m_grow_on_next_insert {false}

bool	m_try_shrink_on_next_insert {false}

Static Private Attributes
static constexpr bool	STORE_HASH

static constexpr bool	USE_STORED_HASH_ON_LOOKUP = StoreHash

static const slz_size_type	SERIALIZATION_PROTOCOL_VERSION = 1

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.

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

◆ 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

◆ 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

private

Initial value:

typename std::allocator_traits<allocator_type>::template rebind_alloc<bucket_entry>

◆ 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

◆ 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>

◆ 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 *

◆ 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 &

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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>

◆ 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

◆ 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

◆ 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 *

◆ 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 &

◆ 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

◆ 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

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 &	my_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 constructor explicit vector(size_type count, const Allocator& alloc = Allocator()); is only available in C++14 and later. We thus must resize after using the vector(const Allocator& alloc) constructor.

We can't use vector(size_type count, const T& value, const Allocator& alloc) as it requires the value T to be copyable.

◆ 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

◆ 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

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::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

◆ 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::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

◆ 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::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	my_hash )

inline

◆ 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::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	my_hash ) const

inline

◆ 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

◆ 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

◆ 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

◆ 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 my_hash ) const

inlineprivate

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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	my_hash ) const

inline

◆ 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

◆ 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	my_hash ) const

inline

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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	my_hash )

inline

◆ 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	my_hash ) const

inline

◆ 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

◆ 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	my_hash )

inline

◆ 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

◆ 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

◆ 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.

◆ 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.

◆ 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

◆ 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

◆ 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	my_hash )

inline

◆ 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	my_hash ) const

inline

◆ 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	my_hash )

inlineprivate

◆ 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	my_hash ) const

inlineprivate

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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	my_hash,
		Args &&...	value_type_args )

inlineprivate

◆ 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	my_hash,
		value_type &&	value )

inlineprivate

◆ 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	my_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.

◆ 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	my_hash,
		value_type &&	value )

inlineprivate

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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::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

◆ 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::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

◆ 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

◆ 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

◆ 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::value >::type * = nullptr>

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

inline

◆ 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 my_count )

inline

◆ 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 my_count )

inlineprivate

◆ 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.

◆ 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 my_count )

inline

◆ 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

◆ 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

◆ 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

◆ 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.

◆ 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

◆ 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

◆ 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

◆ 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.

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

◆ 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

◆ 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

◆ 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.

◆ 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.

◆ 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

◆ 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 {false}

private

◆ 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 {0}

private

◆ 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

◆ 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

◆ 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 {0}

private

◆ 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 {false}

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.

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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 currently used for serialization.

◆ 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.

◆ 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.

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

src/robin_hash.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ bucket_entry

◆ buckets_allocator

◆ buckets_container_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ difference_type

◆ distance_type

◆ has_mapped_type

◆ hasher

◆ iterator

◆ key_equal

◆ key_type

◆ pointer

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ robin_hash() [1/3]

◆ robin_hash() [2/3]

◆ robin_hash() [3/3]

Member Function Documentation

◆ at() [1/4]

◆ at() [2/4]

◆ at() [3/4]

◆ at() [4/4]

◆ begin() [1/2]

◆ begin() [2/2]

◆ bucket_count()

◆ bucket_for_hash()

◆ cbegin()

◆ cend()

◆ clear()

◆ clear_and_shrink()

◆ compare_keys()

◆ contains() [1/2]

◆ contains() [2/2]

◆ count() [1/2]

◆ count() [2/2]

◆ deserialize()

◆ deserialize_impl()

◆ emplace()

◆ emplace_hint()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/4]

◆ equal_range() [2/4]

◆ equal_range() [3/4]

◆ equal_range() [4/4]

◆ erase() [1/5]

◆ erase() [2/5]

◆ erase() [3/5]

◆ erase() [4/5]

◆ erase() [5/5]

◆ erase_from_bucket()

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ find_impl() [1/2]

◆ find_impl() [2/2]

◆ get_allocator()

◆ hash_function()

◆ hash_key()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_hint()