Inheritance diagram for std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >:

[legend]

Public Types
typedef _Alloc	allocator_type

using	const_iterator = typename __insert_base::const_iterator

using	const_local_iterator = __detail::_Local_const_iterator< key_type, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __constant_iterators::value, __hash_cached::value >

typedef __value_alloc_traits::const_pointer	const_pointer

typedef const value_type &	const_reference

using	difference_type = typename __hashtable_base::difference_type

typedef _Hash	hasher

using	insert_return_type = _Node_insert_return< iterator, node_type >

using	iterator = typename __insert_base::iterator

typedef _Equal	key_equal

typedef _Key	key_type

using	local_iterator = __detail::_Local_iterator< key_type, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __constant_iterators::value, __hash_cached::value >

using	node_type = _Node_handle< _Key, _Value, __node_alloc_type >

typedef __value_alloc_traits::pointer	pointer

typedef value_type &	reference

using	size_type = typename __hashtable_base::size_type

typedef _Value	value_type

Public Member Functions
	_Hashtable (_Hashtable &&__ht) noexcept(_S_nothrow_move())

	_Hashtable (_Hashtable &&__ht, const allocator_type &__a) noexcept(_S_nothrow_move< __node_alloc_traits::_S_always_equal()>())

template<typename _InputIterator >
	_Hashtable (_InputIterator __f, _InputIterator __l, size_type __bkt_count_hint=0, const _Hash &__hf=_Hash(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())

	_Hashtable (const _Hashtable &)

	_Hashtable (const _Hashtable &, const allocator_type &)

	_Hashtable (const allocator_type &__a)

	_Hashtable (initializer_list< value_type > __l, size_type __bkt_count_hint=0, const _Hash &__hf=_Hash(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())

	_Hashtable (size_type __bkt_count_hint, const _Hash &__hf=_Hash(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())

const _RehashPolicy &	__rehash_policy () const

void	__rehash_policy (const _RehashPolicy &__pol)

template<typename... _Args>
auto	_M_emplace (const_iterator __hint, false_type, _Args &&... __args) -> iterator

template<typename... _Args>
auto	_M_emplace (true_type, _Args &&... __args) -> pair< iterator, bool >

template<typename _Kt >
auto	_M_find_before_node_tr (size_type __bkt, const _Kt &__k, __hash_code __code) const -> __node_base_ptr

template<typename _Arg , typename _NodeGenerator >
auto	_M_insert (_Arg &&__v, const _NodeGenerator &__node_gen, true_type) -> pair< iterator, bool >

template<typename _Arg , typename _NodeGenerator >
auto	_M_insert (const_iterator __hint, _Arg &&__v, const _NodeGenerator &__node_gen, false_type) -> iterator

template<typename _Compatible_Hashtable >
void	_M_merge_multi (_Compatible_Hashtable &__src) noexcept

template<typename _Compatible_Hashtable >
void	_M_merge_unique (_Compatible_Hashtable &__src) noexcept

insert_return_type	_M_reinsert_node (node_type &&__nh)

iterator	_M_reinsert_node_multi (const_iterator __hint, node_type &&__nh)

const_iterator	begin () const noexcept

iterator	begin () noexcept

local_iterator	begin (size_type __bkt)

const_local_iterator	begin (size_type __bkt) const

size_type	bucket (const key_type &__k) const

size_type	bucket_count () const noexcept

size_type	bucket_size (size_type __bkt) const

const_iterator	cbegin () const noexcept

const_local_iterator	cbegin (size_type __bkt) const

const_iterator	cend () const noexcept

const_local_iterator	cend (size_type __bkt) const

void	clear () noexcept

size_type	count (const key_type &__k) const

template<typename... _Args>
__ireturn_type	emplace (_Args &&... __args)

template<typename... _Args>
iterator	emplace_hint (const_iterator __hint, _Args &&... __args)

bool	empty () const noexcept

const_iterator	end () const noexcept

iterator	end () noexcept

local_iterator	end (size_type __bkt)

const_local_iterator	end (size_type __bkt) const

std::pair< iterator, iterator >	equal_range (const key_type &__k)

std::pair< const_iterator, const_iterator >	equal_range (const key_type &__k) const

size_type	erase (const key_type &__k)

iterator	erase (const_iterator)

iterator	erase (const_iterator, const_iterator)

iterator	erase (iterator __it)

node_type	extract (const _Key &__k)

node_type	extract (const_iterator __pos)

iterator	find (const key_type &__k)

const_iterator	find (const key_type &__k) const

allocator_type	get_allocator () const noexcept

hasher	hash_function () const

key_equal	key_eq () const

float	load_factor () const noexcept

size_type	max_bucket_count () const noexcept

size_type	max_size () const noexcept

_Hashtable &	operator= (_Hashtable &&__ht) noexcept(__node_alloc_traits::_S_nothrow_move() &&is_nothrow_move_assignable< _Hash >::value &&is_nothrow_move_assignable< _Equal >::value)

_Hashtable &	operator= (const _Hashtable &__ht)

_Hashtable &	operator= (initializer_list< value_type > __l)

void	rehash (size_type __bkt_count)

size_type	size () const noexcept

void	swap (_Hashtable &) noexcept(__and_< __is_nothrow_swappable< _Hash >, __is_nothrow_swappable< _Equal >>::value)

Protected Member Functions
std::size_t	_M_bucket_index (__hash_code __c, std::size_t __bkt_count) const

std::size_t	_M_bucket_index (const _Hash_node_value< _Value, false > &__n, std::size_t __bkt_count) const noexcept(noexcept(declval< const _Hash & >()(declval< const _Key & >())) &&noexcept(declval< const _RangeHash & >()((__hash_code) 0,(std::size_t) 0)))

std::size_t	_M_bucket_index (const _Hash_node_value< _Value, true > &__n, std::size_t __bkt_count) const noexcept(noexcept(declval< const _RangeHash & >()((__hash_code) 0,(std::size_t) 0)))

void	_M_copy_code (_Hash_node_code_cache< false > &, const _Hash_node_code_cache< false > &) const

void	_M_copy_code (_Hash_node_code_cache< true > &__to, const _Hash_node_code_cache< true > &__from) const

const _Equal &	_M_eq () const

bool	_M_equals (const _Key &__k, __hash_code __c, const _Hash_node_value< _Value, __hash_cached::value > &__n) const

template<typename _Kt >
bool	_M_equals_tr (const _Kt &__k, __hash_code __c, const _Hash_node_value< _Value, __hash_cached::value > &__n) const

const _Hash &	_M_hash () const

__hash_code	_M_hash_code (const _Key &__k) const

__hash_code	_M_hash_code_tr (const _Kt &__k) const

bool	_M_node_equals (const _Hash_node_value< _Value, __hash_cached::value > &__lhn, const _Hash_node_value< _Value, __hash_cached::value > &__rhn) const

void	_M_store_code (_Hash_node_code_cache< false > &, __hash_code) const

void	_M_store_code (_Hash_node_code_cache< true > &__n, __hash_code __c) const

void	_M_swap (_Hash_code_base &__x)

void	_M_swap (_Hashtable_base &__x)

Friends
template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _Hasha , typename _RangeHasha , typename _Unuseda , typename _RehashPolicya , typename _Traitsa , bool _Unique_keysa>
struct	__detail::_Equality

template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _Hasha , typename _RangeHasha , typename _Unuseda , typename _RehashPolicya , typename _Traitsa , bool _Constant_iteratorsa>
struct	__detail::_Insert

template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _Hasha , typename _RangeHasha , typename _Unuseda , typename _RehashPolicya , typename _Traitsa >
struct	__detail::_Insert_base

template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _Hasha , typename _RangeHasha , typename _Unuseda , typename _RehashPolicya , typename _Traitsa , bool _Unique_keysa>
struct	__detail::_Map_base

Detailed Description

template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits>
class std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >

Primary class template _Hashtable.

Template Parameters

_Value	CopyConstructible type.
_Key	CopyConstructible type.
_Alloc	An allocator type ([lib.allocator.requirements]) whose _Alloc::value_type is _Value. As a conforming extension, we allow for _Alloc::value_type != _Value.
_ExtractKey	Function object that takes an object of type _Value and returns a value of type _Key.
_Equal	Function object that takes two objects of type k and returns a bool-like value that is true if the two objects are considered equal.
_Hash	The hash function. A unary function object with argument type _Key and result type size_t. Return values should be distributed over the entire range [0, numeric_limits<size_t>:::max()].
_RangeHash	The range-hashing function (in the terminology of Tavori and Dreizin). A binary function object whose argument types and result type are all size_t. Given arguments r and N, the return value is in the range [0, N).
_Unused	Not used.
_RehashPolicy	Policy class with three members, all of which govern the bucket count. _M_next_bkt(n) returns a bucket count no smaller than n. _M_bkt_for_elements(n) returns a bucket count appropriate for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the current bucket count is n_bkt and the current element count is n_elt, we need to increase the bucket count for n_ins insertions. If so, returns make_pair(true, n), where n is the new bucket count. If not, returns make_pair(false, <anything>)
_Traits	Compile-time class with three boolean std::integral_constant members: __cache_hash_code, __constant_iterators, __unique_keys.

Each _Hashtable data structure has:

_Bucket[] _M_buckets
_Hash_node_base _M_before_begin
size_type _M_bucket_count
size_type _M_element_count

with _Bucket being _Hash_node_base* and _Hash_node containing:

_Hash_node* _M_next
Tp _M_value
size_t _M_hash_code if cache_hash_code is true

In terms of Standard containers the hashtable is like the aggregation of:

std::forward_list<_Node> containing the elements
std::vector<std::forward_list<_Node>::iterator> representing the buckets

The non-empty buckets contain the node before the first node in the bucket. This design makes it possible to implement something like a std::forward_list::insert_after on container insertion and std::forward_list::erase_after on container erase calls. _M_before_begin is equivalent to std::forward_list::before_begin. Empty buckets contain nullptr. Note that one of the non-empty buckets contains &_M_before_begin which is not a dereferenceable node so the node pointer in a bucket shall never be dereferenced, only its next node can be.

Walking through a bucket's nodes requires a check on the hash code to see if each node is still in the bucket. Such a design assumes a quite efficient hash functor and is one of the reasons it is highly advisable to set __cache_hash_code to true.

The container iterators are simply built from nodes. This way incrementing the iterator is perfectly efficient independent of how many empty buckets there are in the container.

On insert we compute the element's hash code and use it to find the bucket index. If the element must be inserted in an empty bucket we add it at the beginning of the singly linked list and make the bucket point to _M_before_begin. The bucket that used to point to _M_before_begin, if any, is updated to point to its new before begin node.

On erase, the simple iterator design requires using the hash functor to get the index of the bucket to update. For this reason, when __cache_hash_code is set to false the hash functor must not throw and this is enforced by a static assertion.

Functionality is implemented by decomposition into base classes, where the derived _Hashtable class is used in _Map_base, _Insert, _Rehash_base, and _Equality base classes to access the "this" pointer. _Hashtable_base is used in the base classes as a non-recursive, fully-completed-type so that detailed nested type information, such as iterator type and node type, can be used. This is similar to the "Curiously Recurring Template Pattern" (CRTP) technique, but uses a reconstructed, not explicitly passed, template pattern.

Base class templates are:

__detail::_Hashtable_base
__detail::_Map_base
__detail::_Insert
__detail::_Rehash_base
__detail::_Equality

Definition at line 168 of file bits/hashtable.h.

Member Function Documentation

◆ _M_merge_multi()

template<typename _Key , typename _Value , typename _Alloc , typename _ExtractKey , typename _Equal , typename _Hash , typename _RangeHash , typename _Unused , typename _RehashPolicy , typename _Traits >

template<typename _Compatible_Hashtable >

void std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >::_M_merge_multi ( _Compatible_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits > & __src )

inlinenoexcept

Merge from a compatible container into one with equivalent keys.

Definition at line 1059 of file bits/hashtable.h.

◆ _M_merge_unique()

template<typename _Key , typename _Value , typename _Alloc , typename _ExtractKey , typename _Equal , typename _Hash , typename _RangeHash , typename _Unused , typename _RehashPolicy , typename _Traits >

template<typename _Compatible_Hashtable >

void std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >::_M_merge_unique ( _Compatible_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits > & __src )

inlinenoexcept

Merge from a compatible container into one with unique keys.

Definition at line 1031 of file bits/hashtable.h.

◆ _M_reinsert_node()

template<typename _Key , typename _Value , typename _Alloc , typename _ExtractKey , typename _Equal , typename _Hash , typename _RangeHash , typename _Unused , typename _RehashPolicy , typename _Traits >

insert_return_type std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >::_M_reinsert_node ( node_type && __nh )

inline

Re-insert an extracted node into a container with unique keys.

Definition at line 939 of file bits/hashtable.h.

References std::end().

Referenced by std::unordered_map< _Key, _Tp, _Hash, _Pred, _Alloc >::insert(), and std::unordered_set< _Value, _Hash, _Pred, _Alloc >::insert().

◆ _M_reinsert_node_multi()

template<typename _Key , typename _Value , typename _Alloc , typename _ExtractKey , typename _Equal , typename _Hash , typename _RangeHash , typename _Unused , typename _RehashPolicy , typename _Traits >

iterator std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >::_M_reinsert_node_multi	(	const_iterator	__hint,
		node_type &&	__nh
	)

inline

Re-insert an extracted node into a container with equivalent keys.

Definition at line 970 of file bits/hashtable.h.

References std::end().

Referenced by std::unordered_multimap< _Key, _Tp, _Hash, _Pred, _Alloc >::insert(), and std::unordered_multiset< _Value, _Hash, _Pred, _Alloc >::insert().

◆ extract()

template<typename _Key , typename _Value , typename _Alloc , typename _ExtractKey , typename _Equal , typename _Hash , typename _RangeHash , typename _Unused , typename _RehashPolicy , typename _Traits >

node_type std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits >::extract ( const _Key & __k )

inline

Extract a node.

Definition at line 1018 of file bits/hashtable.h.

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

bits/hashtable.h

Public Types

Public Member Functions

Protected Member Functions

Friends

Detailed Description

Member Function Documentation

◆ _M_merge_multi()

◆ _M_merge_unique()

◆ _M_reinsert_node()

◆ _M_reinsert_node_multi()

◆ extract()