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 hopscotch_(sc)_map and hopscotch_(sc)_set.

ValueType is what will be stored by hopscotch_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 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>.

Definition at line 634 of file hopscotch_hash.h.

#include <hopscotch_hash.h>

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

Data Structures
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 &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 &hash, const KeyEqual &equal, const Allocator &alloc, float max_load_factor, const typename OC::key_compare &comp)

	hopscotch_hash (const hopscotch_hash &other)=default

	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)=default

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 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 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 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 hash) const

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

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

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

template<class K >
const_iterator	find (const K &key, std::size_t 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 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 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

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 = 16

static constexpr float	DEFAULT_MAX_LOAD_FACTOR = 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 = tsl::detail_hopscotch_hash::hopscotch_bucket< ValueType, NeighborhoodSize, StoreHash >

using	neighborhood_bitmap = typename hopscotch_bucket::neighborhood_bitmap

using	buckets_allocator = typename std::allocator_traits< allocator_type >::template rebind_alloc< hopscotch_bucket >

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 hash) const

iterator	mutable_iterator (const_iterator pos)

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 (iterator_buckets pos, 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 P >
std::pair< iterator, bool >	insert_impl (P &&value, std::size_t hash, std::size_t ibucket_for_hash)

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 P >
iterator_buckets	insert_in_bucket (P &&value, std::size_t hash, std::size_t ibucket_empty, std::size_t ibucket_for_hash)

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 hash, iterator_buckets it_bucket)

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 hash, const_iterator_buckets it_bucket) const

template<class K >
size_type	count_impl (const K &key, std::size_t hash, const_iterator_buckets it_bucket) const

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

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

template<class K >
iterator_buckets	find_in_buckets (const K &key, std::size_t hash, iterator_buckets it_bucket)

template<class K >
const_iterator_buckets	find_in_buckets (const K &key, std::size_t hash, const_iterator_buckets it_bucket) 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)

Private Attributes
buckets_container_type	m_buckets

overflow_container_type	m_overflow_elements

size_type	m_nb_elements

float	m_max_load_factor

size_type	m_load_threshold

size_type	m_min_load_factor_rehash_threshold

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

static const bool	USE_STORED_HASH_ON_REHASH