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
Merge from a compatible container into one with equivalent keys. template<typename _Compatible_Hashtable > void _M_merge_unique (_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with unique keys. insert_return_type _M_reinsert_node (node_type &&__nh)
Re-insert an extracted node into a container with unique keys. iterator _M_reinsert_node_multi (const_iterator __hint, node_type &&__nh)
Re-insert an extracted node into a container with equivalent keys. 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)
Extract a node. 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

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

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 179 of file bits/hashtable.h.

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) [inline], [noexcept]¶

Merge from a compatible container into one with equivalent keys.

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

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) [inline], [noexcept]¶

Merge from a compatible container into one with unique keys.

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

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 955 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().

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 986 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().

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 1034 of file bits/hashtable.h.