tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer > Class Template Reference

#include <hopscotch_hash.h>

Inheritance diagram for tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >:

Collaboration diagram for tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >:

Classes
class	hopscotch_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 = hopscotch_iterator<false>
using	const_iterator = hopscotch_iterator<true>

Public Member Functions
template<class OC = OverflowContainer, typename std::enable_if<!has_key_compare< OC >::value >::type * = nullptr>
	hopscotch_hash (size_type bucket_count, const Hash &my_hash, const KeyEqual &equal, const Allocator &alloc, float max_load_factor)
template<class OC = OverflowContainer, typename std::enable_if< has_key_compare< OC >::value >::type * = nullptr>
	hopscotch_hash (size_type bucket_count, const Hash &p_hash, const KeyEqual &equal, const Allocator &alloc, float max_load_factor, const typename OC::key_compare &comp)
	hopscotch_hash (const hopscotch_hash &other)
	hopscotch_hash (hopscotch_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 &&std::is_nothrow_move_constructible< overflow_container_type >::value)
hopscotch_hash &	operator= (const hopscotch_hash &other)
hopscotch_hash &	operator= (hopscotch_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
std::pair< iterator, bool >	insert (const value_type &value)
template<class P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type * = nullptr>
std::pair< iterator, bool >	insert (P &&value)
std::pair< iterator, bool >	insert (value_type &&value)
iterator	insert (const_iterator hint, const value_type &value)
template<class P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type * = nullptr>
iterator	insert (const_iterator hint, P &&value)
iterator	insert (const_iterator hint, value_type &&value)
template<class InputIt >
void	insert (InputIt first, InputIt last)
template<class M >
std::pair< iterator, bool >	insert_or_assign (const key_type &k, M &&obj)
template<class M >
std::pair< iterator, bool >	insert_or_assign (key_type &&k, M &&obj)
template<class M >
iterator	insert_or_assign (const_iterator hint, const key_type &k, M &&obj)
template<class M >
iterator	insert_or_assign (const_iterator hint, key_type &&k, M &&obj)
template<class... Args>
std::pair< iterator, bool >	emplace (Args &&...args)
template<class... Args>
iterator	emplace_hint (const_iterator hint, Args &&...args)
template<class... Args>
std::pair< iterator, bool >	try_emplace (const key_type &k, Args &&...args)
template<class... Args>
std::pair< iterator, bool >	try_emplace (key_type &&k, Args &&...args)
template<class... Args>
iterator	try_emplace (const_iterator hint, const key_type &k, Args &&...args)
template<class... Args>
iterator	try_emplace (const_iterator hint, key_type &&k, Args &&...args)
iterator	erase (iterator pos)
iterator	erase (const_iterator pos)
iterator	erase (const_iterator first, const_iterator last)
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 (hopscotch_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	max_load_factor () const
void	max_load_factor (float ml)
void	rehash (size_type count_)
void	reserve (size_type count_)
hasher	hash_function () const
key_equal	key_eq () const
iterator	mutable_iterator (const_iterator pos)
size_type	overflow_size () const noexcept
template<class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>
U::key_compare	key_comp () const

Static Public Attributes
static const size_type	DEFAULT_INIT_BUCKETS_SIZE = 0
static constexpr float	DEFAULT_MAX_LOAD_FACTOR = (NeighborhoodSize <= 30) ? 0.8f : 0.9f

Private Types
template<typename U >
using	has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>
using	hopscotch_bucket
using	neighborhood_bitmap = typename hopscotch_bucket::neighborhood_bitmap
using	buckets_allocator
using	buckets_container_type = std::vector<hopscotch_bucket, buckets_allocator>
using	overflow_container_type = OverflowContainer
using	iterator_buckets = typename buckets_container_type::iterator
using	const_iterator_buckets = typename buckets_container_type::const_iterator
using	iterator_overflow = typename overflow_container_type::iterator
using	const_iterator_overflow = typename overflow_container_type::const_iterator

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<typename U = value_type, typename std::enable_if< std::is_nothrow_move_constructible< U >::value >::type * = nullptr>
void	rehash_impl (size_type count_)
template<typename U = value_type, typename std::enable_if< std::is_copy_constructible< U >::value &&!std::is_nothrow_move_constructible< U >::value >::type * = nullptr>
void	rehash_impl (size_type count_)
iterator_overflow	mutable_overflow_iterator (const_iterator_overflow it)
iterator_overflow	erase_from_overflow (const_iterator_overflow pos, std::size_t ibucket_for_hash)
void	erase_from_bucket (hopscotch_bucket &bucket_for_value, std::size_t ibucket_for_hash) noexcept
template<class K , class M >
std::pair< iterator, bool >	insert_or_assign_impl (K &&key, M &&obj)
template<typename P , class... Args>
std::pair< iterator, bool >	try_emplace_impl (P &&key, Args &&...args_value)
template<typename P >
std::pair< iterator, bool >	insert_impl (P &&value)
template<typename... Args>
std::pair< iterator, bool >	insert_value (std::size_t ibucket_for_hash, std::size_t my_hash, Args &&...value_type_args)
bool	will_neighborhood_change_on_rehash (size_t ibucket_neighborhood_check) const
std::size_t	find_empty_bucket (std::size_t ibucket_start) const
template<typename... Args>
iterator_buckets	insert_in_bucket (std::size_t ibucket_empty, std::size_t ibucket_for_hash, std::size_t my_hash, Args &&...value_type_args)
template<class... Args, class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>
iterator_overflow	insert_in_overflow (std::size_t ibucket_for_hash, Args &&...value_type_args)
template<class... Args, class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>
iterator_overflow	insert_in_overflow (std::size_t ibucket_for_hash, Args &&...value_type_args)
bool	swap_empty_bucket_closer (std::size_t &ibucket_empty_in_out)
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
U::value_type *	find_value_impl (const K &key, std::size_t my_hash, hopscotch_bucket *bucket_for_hash)
template<class K , class U = ValueSelect, typename std::enable_if< has_mapped_type< U >::value >::type * = nullptr>
const U::value_type *	find_value_impl (const K &key, std::size_t my_hash, const hopscotch_bucket *bucket_for_hash) const
template<class K >
size_type	count_impl (const K &key, std::size_t my_hash, const hopscotch_bucket *bucket_for_hash) const
template<class K >
iterator	find_impl (const K &key, std::size_t my_hash, hopscotch_bucket *bucket_for_hash)
template<class K >
const_iterator	find_impl (const K &key, std::size_t my_hash, const hopscotch_bucket *bucket_for_hash) const
template<class K >
hopscotch_bucket *	find_in_buckets (const K &key, std::size_t my_hash, hopscotch_bucket *bucket_for_hash)
template<class K >
const hopscotch_bucket *	find_in_buckets (const K &key, std::size_t my_hash, const hopscotch_bucket *bucket_for_hash) const
template<class K , class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>
iterator_overflow	find_in_overflow (const K &key)
template<class K , class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>
const_iterator_overflow	find_in_overflow (const K &key) const
template<class K , class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>
iterator_overflow	find_in_overflow (const K &key)
template<class K , class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>
const_iterator_overflow	find_in_overflow (const K &key) const
template<class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>
hopscotch_hash	new_hopscotch_hash (size_type bucket_count)
template<class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>
hopscotch_hash	new_hopscotch_hash (size_type bucket_count)
hopscotch_bucket *	static_empty_bucket_ptr ()

Static Private Member Functions
template<class T = size_type, typename std::enable_if< std::is_same< T, truncated_hash_type >::value >::type * = nullptr>
static bool	USE_STORED_HASH_ON_REHASH (size_type)
template<class T = size_type, typename std::enable_if<!std::is_same< T, truncated_hash_type >::value >::type * = nullptr>
static bool	USE_STORED_HASH_ON_REHASH (size_type bucket_count)

Private Attributes
buckets_container_type	m_buckets_data
overflow_container_type	m_overflow_elements
hopscotch_bucket *	m_buckets
size_type	m_nb_elements
size_type	m_min_load_threshold_rehash
size_type	m_max_load_threshold_rehash
float	m_max_load_factor

Static Private Attributes
static const std::size_t	MAX_PROBES_FOR_EMPTY_BUCKET = 12 * NeighborhoodSize
static constexpr float	MIN_LOAD_FACTOR_FOR_REHASH = 0.1f

Detailed Description

template<class ValueType, class KeySelect, class ValueSelect, class Hash, class KeyEqual, class Allocator, unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy, class OverflowContainer>
class tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >

Internal common class used by (b)hopscotch_map and (b)hopscotch_set.

ValueType is what will be stored by hopscotch_hash (usually std::pair<Key, T> for a map and Key for a 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).

OverflowContainer will be used as containers for overflown elements. Usually it should be a list<ValueType> or a set<Key>/map<Key, T>.

Member Typedef Documentation

allocator_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::allocator_type = Allocator

buckets_allocator

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::buckets_allocator

private

Initial value:

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

buckets_container_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::buckets_container_type = std::vector<hopscotch_bucket, buckets_allocator>

private

const_iterator

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::const_iterator = hopscotch_iterator<true>

const_iterator_buckets

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::const_iterator_buckets = typename buckets_container_type::const_iterator

private

const_iterator_overflow

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::const_iterator_overflow = typename overflow_container_type::const_iterator

private

const_pointer

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::const_pointer = const value_type *

const_reference

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::const_reference = const value_type &

difference_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::difference_type = std::ptrdiff_t

has_mapped_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename U >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hasher = Hash

hopscotch_bucket

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hopscotch_bucket

private

Initial value:

 
          tsl::detail_hopscotch_hash::hopscotch_bucket<ValueType, NeighborhoodSize, StoreHash>

iterator

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::iterator = hopscotch_iterator<false>

iterator_buckets

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::iterator_buckets = typename buckets_container_type::iterator

private

iterator_overflow

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::iterator_overflow = typename overflow_container_type::iterator

private

key_equal

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::key_equal = KeyEqual

key_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::key_type = typename KeySelect::key_type

neighborhood_bitmap

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::neighborhood_bitmap = typename hopscotch_bucket::neighborhood_bitmap

private

overflow_container_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::overflow_container_type = OverflowContainer

private

pointer

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::pointer = value_type *

reference

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::reference = value_type &

size_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::size_type = std::size_t

value_type

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

using tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::value_type = ValueType

Constructor & Destructor Documentation

hopscotch_hash() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class OC = OverflowContainer, typename std::enable_if<!has_key_compare< OC >::value >::type * = nullptr>

tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hopscotch_hash ( size_type bucket_count, const Hash & my_hash, const KeyEqual & equal, const Allocator & alloc, float max_load_factor )

inline

hopscotch_hash() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class OC = OverflowContainer, typename std::enable_if< has_key_compare< OC >::value >::type * = nullptr>

tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hopscotch_hash ( size_type bucket_count, const Hash & p_hash, const KeyEqual & equal, const Allocator & alloc, float max_load_factor, const typename OC::key_compare & comp )

inline

hopscotch_hash() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hopscotch_hash ( const hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer > & other )

inline

hopscotch_hash() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hopscotch_hash ( hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer > && other )

inlinenoexcept

Member Function Documentation

at() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

U::value_type & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::at ( const K & key )

inline

at() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

const U::value_type & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::at ( const K & key ) const

inline

at() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

U::value_type & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

const U::value_type & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::begin ( ) const

inlinenoexcept

begin() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::begin ( )

inlinenoexcept

bucket_count()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::bucket_count ( ) const

inline

bucket_for_hash()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

std::size_t tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::bucket_for_hash ( std::size_t my_hash ) const

inlineprivate

cbegin()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::cbegin ( ) const

inlinenoexcept

cend()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::cend ( ) const

inlinenoexcept

clear()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::clear ( )

inlinenoexcept

compare_keys()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K1 , class K2 >

bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::contains ( const K & key ) const

inline

contains() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::count ( const K & key ) const

inline

count() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::count ( const K & key, std::size_t my_hash ) const

inline

count_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::count_impl ( const K & key, std::size_t my_hash, const hopscotch_bucket * bucket_for_hash ) const

inlineprivate

emplace()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args>

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

inline

emplace_hint()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args>

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::emplace_hint ( const_iterator hint, Args &&... args )

inline

empty()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::empty ( ) const

inlinenoexcept

end() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::end ( ) const

inlinenoexcept

end() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::end ( )

inlinenoexcept

equal_range() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

std::pair< iterator, iterator > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::equal_range ( const K & key )

inline

equal_range() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

std::pair< const_iterator, const_iterator > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::equal_range ( const K & key ) const

inline

equal_range() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

std::pair< iterator, iterator > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

std::pair< const_iterator, const_iterator > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::erase ( const K & key )

inline

erase() [2/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::erase ( const_iterator first, const_iterator last )

inline

erase() [4/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::erase ( const_iterator pos )

inline

erase() [5/5]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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_from_bucket()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::erase_from_bucket ( hopscotch_bucket & bucket_for_value, std::size_t ibucket_for_hash )

inlineprivatenoexcept

bucket_for_value is the bucket in which the value is. ibucket_for_hash is the bucket where the value belongs.

erase_from_overflow()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::erase_from_overflow ( const_iterator_overflow pos, std::size_t ibucket_for_hash )

inlineprivate

find() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find ( const K & key )

inline

find() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find ( const K & key ) const

inline

find() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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 , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find ( const K & key, std::size_t my_hash ) const

inline

find_empty_bucket()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

std::size_t tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_empty_bucket ( std::size_t ibucket_start ) const

inlineprivate

find_impl() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

const_iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_impl ( const K & key, std::size_t my_hash, const hopscotch_bucket * bucket_for_hash ) const

inlineprivate

find_impl() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_impl ( const K & key, std::size_t my_hash, hopscotch_bucket * bucket_for_hash )

inlineprivate

find_in_buckets() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

const hopscotch_bucket * tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_in_buckets ( const K & key, std::size_t my_hash, const hopscotch_bucket * bucket_for_hash ) const

inlineprivate

Return a pointer to the bucket which has the value, nullptr otherwise.

find_in_buckets() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

hopscotch_bucket * tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_in_buckets ( const K & key, std::size_t my_hash, hopscotch_bucket * bucket_for_hash )

inlineprivate

find_in_overflow() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K , class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>

iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_in_overflow ( const K & key )

inlineprivate

find_in_overflow() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_in_overflow ( const K & key )

inlineprivate

find_in_overflow() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K , class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>

const_iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_in_overflow ( const K & key ) const

inlineprivate

find_in_overflow() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

const_iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_in_overflow ( const K & key ) const

inlineprivate

find_value_impl() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

const U::value_type * tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_value_impl ( const K & key, std::size_t my_hash, const hopscotch_bucket * bucket_for_hash ) const

inlineprivate

find_value_impl() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

U::value_type * tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::find_value_impl ( const K & key, std::size_t my_hash, hopscotch_bucket * bucket_for_hash )

inlineprivate

get_allocator()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

allocator_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::get_allocator ( ) const

inline

hash_function()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

hasher tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hash_function ( ) const

inline

hash_key()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K >

std::size_t tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::hash_key ( const K & key ) const

inlineprivate

insert() [1/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( const value_type & value )

inline

insert() [2/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( const_iterator hint, const value_type & value )

inline

insert() [3/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type * = nullptr>

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( const_iterator hint, P && value )

inline

insert() [4/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( const_iterator hint, value_type && value )

inline

insert() [5/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class InputIt >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( InputIt first, InputIt last )

inline

insert() [6/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type * = nullptr>

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( P && value )

inline

insert() [7/7]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert ( value_type && value )

inline

insert_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename P >

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_impl ( P && value )

inlineprivate

insert_in_bucket()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename... Args>

iterator_buckets tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_in_bucket ( std::size_t ibucket_empty, std::size_t ibucket_for_hash, std::size_t my_hash, Args &&... value_type_args )

inlineprivate

insert_in_overflow() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args, class U = OverflowContainer, typename std::enable_if<!has_key_compare< U >::value >::type * = nullptr>

iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_in_overflow ( std::size_t ibucket_for_hash, Args &&... value_type_args )

inlineprivate

insert_in_overflow() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args, class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>

iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_in_overflow ( std::size_t ibucket_for_hash, Args &&... value_type_args )

inlineprivate

insert_or_assign() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class M >

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_or_assign ( const key_type & k, M && obj )

inline

insert_or_assign() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class M >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_or_assign ( const_iterator hint, const key_type & k, M && obj )

inline

insert_or_assign() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class M >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_or_assign ( const_iterator hint, key_type && k, M && obj )

inline

insert_or_assign() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class M >

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_or_assign ( key_type && k, M && obj )

inline

insert_or_assign_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class K , class M >

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_or_assign_impl ( K && key, M && obj )

inlineprivate

insert_value()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename... Args>

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::insert_value ( std::size_t ibucket_for_hash, std::size_t my_hash, Args &&... value_type_args )

inlineprivate

key_comp()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>

U::key_compare tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::key_comp ( ) const

inline

key_eq()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

key_equal tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::key_eq ( ) const

inline

load_factor()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

float tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::load_factor ( ) const

inline

max_bucket_count()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::max_bucket_count ( ) const

inline

max_load_factor() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

float tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::max_load_factor ( ) const

inline

max_load_factor() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::max_load_factor ( float ml )

inline

max_size()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::max_size ( ) const

inlinenoexcept

mutable_iterator()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::mutable_iterator ( const_iterator pos )

inline

mutable_overflow_iterator()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

iterator_overflow tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::mutable_overflow_iterator ( const_iterator_overflow it )

inlineprivate

new_hopscotch_hash() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

hopscotch_hash tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::new_hopscotch_hash ( size_type bucket_count )

inlineprivate

new_hopscotch_hash() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class U = OverflowContainer, typename std::enable_if< has_key_compare< U >::value >::type * = nullptr>

hopscotch_hash tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::new_hopscotch_hash ( size_type bucket_count )

inlineprivate

operator=() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

hopscotch_hash & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::operator= ( const hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer > & other )

inline

operator=() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

hopscotch_hash & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::operator= ( hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer > && other )

inline

operator[]()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

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

U::value_type & tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::operator[] ( K && key )

inline

overflow_size()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::overflow_size ( ) const

inlinenoexcept

rehash()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::rehash ( size_type count_ )

inline

rehash_impl() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename U = value_type, typename std::enable_if< std::is_nothrow_move_constructible< U >::value >::type * = nullptr>

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::rehash_impl ( size_type count_ )

inlineprivate

rehash_impl() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename U = value_type, typename std::enable_if< std::is_copy_constructible< U >::value &&!std::is_nothrow_move_constructible< U >::value >::type * = nullptr>

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::rehash_impl ( size_type count_ )

inlineprivate

reserve()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::reserve ( size_type count_ )

inline

size()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::size ( ) const

inlinenoexcept

static_empty_bucket_ptr()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

hopscotch_bucket * tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::static_empty_bucket_ptr ( )

inlineprivate

Return an always valid pointer to an static empty hopscotch_bucket.

swap()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

void tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::swap ( hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer > & other )

inline

swap_empty_bucket_closer()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::swap_empty_bucket_closer ( std::size_t & ibucket_empty_in_out )

inlineprivate

try_emplace() [1/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args>

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::try_emplace ( const key_type & k, Args &&... args )

inline

try_emplace() [2/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args>

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::try_emplace ( const_iterator hint, const key_type & k, Args &&... args )

inline

try_emplace() [3/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args>

iterator tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::try_emplace ( const_iterator hint, key_type && k, Args &&... args )

inline

try_emplace() [4/4]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class... Args>

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::try_emplace ( key_type && k, Args &&... args )

inline

try_emplace_impl()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<typename P , class... Args>

std::pair< iterator, bool > tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::try_emplace_impl ( P && key, Args &&... args_value )

inlineprivate

USE_STORED_HASH_ON_REHASH() [1/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class T = size_type, typename std::enable_if<!std::is_same< T, truncated_hash_type >::value >::type * = nullptr>

static bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::USE_STORED_HASH_ON_REHASH ( size_type bucket_count )

inlinestaticprivate

USE_STORED_HASH_ON_REHASH() [2/2]

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

template<class T = size_type, typename std::enable_if< std::is_same< T, truncated_hash_type >::value >::type * = nullptr>

static bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::USE_STORED_HASH_ON_REHASH ( size_type )

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 too much bytes.

will_neighborhood_change_on_rehash()

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

bool tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::will_neighborhood_change_on_rehash ( size_t ibucket_neighborhood_check ) const

inlineprivate

Member Data Documentation

DEFAULT_INIT_BUCKETS_SIZE

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

const size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::DEFAULT_INIT_BUCKETS_SIZE = 0

static

DEFAULT_MAX_LOAD_FACTOR

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

float tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::DEFAULT_MAX_LOAD_FACTOR = (NeighborhoodSize <= 30) ? 0.8f : 0.9f

staticconstexpr

m_buckets

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

hopscotch_bucket* tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::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+size instead of a pointer+vector to save some space in the hopscotch_hash object.

m_buckets_data

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

buckets_container_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::m_buckets_data

private

m_max_load_factor

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

float tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::m_max_load_factor

private

m_max_load_threshold_rehash

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::m_max_load_threshold_rehash

private

Max size of the hash table before a rehash occurs automatically to grow the table.

m_min_load_threshold_rehash

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::m_min_load_threshold_rehash

private

Min size of the hash table before a rehash can occurs automatically (except if m_max_load_threshold_rehash os reached). If the neighborhood of a bucket is full before the min is reached, the elements are put into m_overflow_elements.

m_nb_elements

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

size_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::m_nb_elements

private

m_overflow_elements

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

overflow_container_type tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::m_overflow_elements

private

MAX_PROBES_FOR_EMPTY_BUCKET

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

const std::size_t tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::MAX_PROBES_FOR_EMPTY_BUCKET = 12 * NeighborhoodSize

staticprivate

MIN_LOAD_FACTOR_FOR_REHASH

template<class ValueType , class KeySelect , class ValueSelect , class Hash , class KeyEqual , class Allocator , unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy , class OverflowContainer >

float tsl::detail_hopscotch_hash::hopscotch_hash< ValueType, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, OverflowContainer >::MIN_LOAD_FACTOR_FOR_REHASH = 0.1f

staticconstexprprivate

---

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

• src/hopscotch_hash.h