Std::_hashtable _key, _value, _alloc, _extractkey, _equal, _h1, _h2, _hash, _rehashpolicy, _traits -
Inherits std::__detail::_Hashtable_base< _Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits >, std::__detail::_Map_base< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >, std::__detail::_Insert< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >, std::__detail::_Rehash_base< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >, std::__detail::_Equality< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >, and std::__detail::_Hashtable_alloc< __alloctr_rebind< _Alloc, __detail::_Hash_node< _Value, _Traits::__hash_cached::value > >::__type >.
typedef _Alloc allocator_type
using const_iterator = __detail::_Node_const_iterator< value_type, __constant_iterators::value, __hash_cached::value >
using const_local_iterator = __detail::_Local_const_iterator< key_type, value_type, _ExtractKey, _H1, _H2, _Hash, __constant_iterators::value, __hash_cached::value >
typedef
__value_alloc_traits::const_pointer const_pointer"
typedef const value_type & const_reference
typedef std::ptrdiff_t difference_type
using iterator = __detail::_Node_iterator< value_type, __constant_iterators::value, __hash_cached::value >
typedef _Equal key_equal
typedef _Key key_type
using local_iterator = __detail::_Local_iterator< key_type, value_type, _ExtractKey, _H1, _H2, _Hash, __constant_iterators::value, __hash_cached::value >
typedef
__value_alloc_traits::pointer pointer"
typedef value_type & reference
typedef std::size_t size_type
typedef _Value value_type
const _Equal & _M_eq () const
_Equal & _M_eq ()
bool _M_equals (const _Key &__k, __hash_code __c, __node_type *__n) const
void _M_swap (_Hashtable_base &__x)
using __bucket_alloc_traits = std::allocator_traits< __bucket_alloc_type >
using __bucket_alloc_type = typename __alloctr_rebind< __node_alloc_type, __bucket_type >::__type
using __value_alloc_type = typename __alloctr_rebind< __node_alloc_type, __value_type >::__type
using __value_type = typename __node_type::value_type
__bucket_type * _M_allocate_buckets (std::size_t __n)
__node_type * _M_allocate_node (_Args &&...__args)
void _M_deallocate_buckets (__bucket_type *, std::size_t __n)
void _M_deallocate_node (__node_type *__n)
void _M_deallocate_nodes (__node_type *__n)
__node_alloc_type & _M_node_allocator ()
const __node_alloc_type & _M_node_allocator () const
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.
_H1 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()].
_H2 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).
_Hash The ranged hash function (Tavori and Dreizin). A binary function whose argument types are _Key and size_t and whose result type is size_t. Given arguments k and N, the return value is in the range [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other than the default, _H1 and _H2 are ignored.
_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. 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* 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 170 of file bits/hashtable.h.
Generated automatically by Doxygen for libstdc++ from the source code.