.TH "std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >" 3cxx "Tue Jul 2 2019" "libstdc++" \" -*- nroff -*-
.ad l
.nh
.SH NAME
std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >
.SH SYNOPSIS
.br
.PP
.PP
Inherits \fBstd::__detail::_Hashtable_base< _Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits >\fP, \fBstd::__detail::_Map_base< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >\fP, \fBstd::__detail::_Insert< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >\fP, \fBstd::__detail::_Rehash_base< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >\fP, \fBstd::__detail::_Equality< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >\fP, and \fBstd::__detail::_Hashtable_alloc< __alloc_rebind< _Alloc, __detail::_Hash_node< _Value, _Traits::__hash_cached::value > > >\fP\&.
.SS "Public Types"

.in +1c
.ti -1c
.RI "typedef _Alloc \fBallocator_type\fP"
.br
.ti -1c
.RI "using \fBconst_iterator\fP = typename \fB__hashtable_base::const_iterator\fP"
.br
.ti -1c
.RI "using \fBconst_local_iterator\fP = typename \fB__hashtable_base::const_local_iterator\fP"
.br
.ti -1c
.RI "typedef __value_alloc_traits::const_pointer \fBconst_pointer\fP"
.br
.ti -1c
.RI "typedef const value_type & \fBconst_reference\fP"
.br
.ti -1c
.RI "using \fBdifference_type\fP = typename __hashtable_base::difference_type"
.br
.ti -1c
.RI "using \fBiterator\fP = typename \fB__hashtable_base::iterator\fP"
.br
.ti -1c
.RI "typedef _Equal \fBkey_equal\fP"
.br
.ti -1c
.RI "typedef _Key \fBkey_type\fP"
.br
.ti -1c
.RI "using \fBlocal_iterator\fP = typename \fB__hashtable_base::local_iterator\fP"
.br
.ti -1c
.RI "typedef __value_alloc_traits::pointer \fBpointer\fP"
.br
.ti -1c
.RI "typedef value_type & \fBreference\fP"
.br
.ti -1c
.RI "using \fBsize_type\fP = typename __hashtable_base::size_type"
.br
.ti -1c
.RI "typedef _Value \fBvalue_type\fP"
.br
.in -1c
.SS "Public Member Functions"

.in +1c
.ti -1c
.RI "\fB_Hashtable\fP (size_type __bucket_hint, const _H1 &, const _H2 &, const _Hash &, const _Equal &, const _ExtractKey &, const allocator_type &)"
.br
.ti -1c
.RI "template<typename _InputIterator > \fB_Hashtable\fP (_InputIterator __first, _InputIterator __last, size_type __bucket_hint, const _H1 &, const _H2 &, const _Hash &, const _Equal &, const _ExtractKey &, const allocator_type &)"
.br
.ti -1c
.RI "\fB_Hashtable\fP (const \fB_Hashtable\fP &)"
.br
.ti -1c
.RI "\fB_Hashtable\fP (\fB_Hashtable\fP &&) noexcept"
.br
.ti -1c
.RI "\fB_Hashtable\fP (const \fB_Hashtable\fP &, const allocator_type &)"
.br
.ti -1c
.RI "\fB_Hashtable\fP (\fB_Hashtable\fP &&, const allocator_type &)"
.br
.ti -1c
.RI "\fB_Hashtable\fP (const allocator_type &__a)"
.br
.ti -1c
.RI "\fB_Hashtable\fP (size_type __n, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())"
.br
.ti -1c
.RI "template<typename _InputIterator > \fB_Hashtable\fP (_InputIterator __f, _InputIterator __l, size_type __n=0, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())"
.br
.ti -1c
.RI "\fB_Hashtable\fP (\fBinitializer_list\fP< value_type > __l, size_type __n=0, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())"
.br
.ti -1c
.RI "const _RehashPolicy & \fB__rehash_policy\fP () const"
.br
.ti -1c
.RI "void \fB__rehash_policy\fP (const _RehashPolicy &__pol)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> auto \fB_M_emplace\fP (\fBstd::true_type\fP, _Args &&\&.\&.\&. __args) \-> \fBpair\fP< iterator, bool >"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> auto \fB_M_emplace\fP (const_iterator __hint, \fBstd::false_type\fP, _Args &&\&.\&.\&. __args) \-> iterator"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGenerator > auto \fB_M_insert\fP (_Arg &&__v, const _NodeGenerator &__node_gen, \fBtrue_type\fP, size_type __n_elt) \-> \fBpair\fP< iterator, bool >"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGenerator > auto \fB_M_insert\fP (const_iterator __hint, _Arg &&__v, const _NodeGenerator &__node_gen, \fBfalse_type\fP) \-> iterator"
.br
.ti -1c
.RI "iterator \fBbegin\fP () noexcept"
.br
.ti -1c
.RI "const_iterator \fBbegin\fP () const noexcept"
.br
.ti -1c
.RI "local_iterator \fBbegin\fP (size_type __n)"
.br
.ti -1c
.RI "const_local_iterator \fBbegin\fP (size_type __n) const"
.br
.ti -1c
.RI "size_type \fBbucket\fP (const key_type &__k) const"
.br
.ti -1c
.RI "size_type \fBbucket_count\fP () const noexcept"
.br
.ti -1c
.RI "size_type \fBbucket_size\fP (size_type __n) const"
.br
.ti -1c
.RI "const_iterator \fBcbegin\fP () const noexcept"
.br
.ti -1c
.RI "const_local_iterator \fBcbegin\fP (size_type __n) const"
.br
.ti -1c
.RI "const_iterator \fBcend\fP () const noexcept"
.br
.ti -1c
.RI "const_local_iterator \fBcend\fP (size_type __n) const"
.br
.ti -1c
.RI "void \fBclear\fP () noexcept"
.br
.ti -1c
.RI "size_type \fBcount\fP (const key_type &__k) const"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> __ireturn_type \fBemplace\fP (_Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fBemplace_hint\fP (const_iterator __hint, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "bool \fBempty\fP () const noexcept"
.br
.ti -1c
.RI "iterator \fBend\fP () noexcept"
.br
.ti -1c
.RI "const_iterator \fBend\fP () const noexcept"
.br
.ti -1c
.RI "local_iterator \fBend\fP (size_type __n)"
.br
.ti -1c
.RI "const_local_iterator \fBend\fP (size_type __n) const"
.br
.ti -1c
.RI "\fBstd::pair\fP< iterator, iterator > \fBequal_range\fP (const key_type &__k)"
.br
.ti -1c
.RI "\fBstd::pair\fP< const_iterator, const_iterator > \fBequal_range\fP (const key_type &__k) const"
.br
.ti -1c
.RI "iterator \fBerase\fP (const_iterator)"
.br
.ti -1c
.RI "iterator \fBerase\fP (iterator __it)"
.br
.ti -1c
.RI "size_type \fBerase\fP (const key_type &__k)"
.br
.ti -1c
.RI "iterator \fBerase\fP (const_iterator, const_iterator)"
.br
.ti -1c
.RI "iterator \fBfind\fP (const key_type &__k)"
.br
.ti -1c
.RI "const_iterator \fBfind\fP (const key_type &__k) const"
.br
.ti -1c
.RI "allocator_type \fBget_allocator\fP () const noexcept"
.br
.ti -1c
.RI "key_equal \fBkey_eq\fP () const"
.br
.ti -1c
.RI "float \fBload_factor\fP () const noexcept"
.br
.ti -1c
.RI "size_type \fBmax_bucket_count\fP () const noexcept"
.br
.ti -1c
.RI "size_type \fBmax_size\fP () const noexcept"
.br
.ti -1c
.RI "\fB_Hashtable\fP & \fBoperator=\fP (const \fB_Hashtable\fP &__ht)"
.br
.ti -1c
.RI "\fB_Hashtable\fP & \fBoperator=\fP (\fB_Hashtable\fP &&__ht) noexcept(__node_alloc_traits::_S_nothrow_move() &&\fBis_nothrow_move_assignable\fP< _H1 >::value &&\fBis_nothrow_move_assignable\fP< _Equal >::value)"
.br
.ti -1c
.RI "\fB_Hashtable\fP & \fBoperator=\fP (\fBinitializer_list\fP< value_type > __l)"
.br
.ti -1c
.RI "void \fBrehash\fP (size_type __n)"
.br
.ti -1c
.RI "size_type \fBsize\fP () const noexcept"
.br
.ti -1c
.RI "void \fBswap\fP (\fB_Hashtable\fP &) noexcept(__and_< __is_nothrow_swappable< _H1 >, __is_nothrow_swappable< _Equal >>::value)"
.br
.in -1c
.SS "Protected Member Functions"

.in +1c
.ti -1c
.RI "size_type \fB_M_bucket_index\fP (\fB__node_type\fP *__n) const noexcept"
.br
.ti -1c
.RI "size_type \fB_M_bucket_index\fP (const key_type &__k, __hash_code __c) const"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> \fBstd::pair\fP< iterator, bool > \fB_M_emplace\fP (\fBstd::true_type\fP, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fB_M_emplace\fP (\fBstd::false_type\fP __uk, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fB_M_emplace\fP (const_iterator, \fBstd::true_type\fP __uk, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fB_M_emplace\fP (const_iterator, \fBstd::false_type\fP, _Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "const _Equal & \fB_M_eq\fP () const"
.br
.ti -1c
.RI "_Equal & \fB_M_eq\fP ()"
.br
.ti -1c
.RI "bool \fB_M_equals\fP (const _Key &__k, __hash_code __c, \fB__node_type\fP *__n) const"
.br
.ti -1c
.RI "size_type \fB_M_erase\fP (\fBstd::true_type\fP, const key_type &)"
.br
.ti -1c
.RI "size_type \fB_M_erase\fP (\fBstd::false_type\fP, const key_type &)"
.br
.ti -1c
.RI "iterator \fB_M_erase\fP (size_type __bkt, __node_base *__prev_n, \fB__node_type\fP *__n)"
.br
.ti -1c
.RI "__node_base * \fB_M_find_before_node\fP (size_type, const key_type &, __hash_code) const"
.br
.ti -1c
.RI "\fB__node_type\fP * \fB_M_find_node\fP (size_type __bkt, const key_type &__key, __hash_code __c) const"
.br
.ti -1c
.RI "__node_base * \fB_M_get_previous_node\fP (size_type __bkt, __node_base *__n)"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGenerator > \fBstd::pair\fP< iterator, bool > \fB_M_insert\fP (_Arg &&, const _NodeGenerator &, \fBtrue_type\fP, size_type=1)"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGenerator > iterator \fB_M_insert\fP (_Arg &&__arg, const _NodeGenerator &__node_gen, \fBfalse_type\fP __uk)"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGenerator > iterator \fB_M_insert\fP (const_iterator, _Arg &&__arg, const _NodeGenerator &__node_gen, \fBtrue_type\fP __uk)"
.br
.ti -1c
.RI "template<typename _Arg , typename _NodeGenerator > iterator \fB_M_insert\fP (const_iterator, _Arg &&, const _NodeGenerator &, \fBfalse_type\fP)"
.br
.ti -1c
.RI "void \fB_M_insert_bucket_begin\fP (size_type, \fB__node_type\fP *)"
.br
.ti -1c
.RI "iterator \fB_M_insert_multi_node\fP (\fB__node_type\fP *__hint, __hash_code __code, \fB__node_type\fP *__n)"
.br
.ti -1c
.RI "iterator \fB_M_insert_unique_node\fP (size_type __bkt, __hash_code __code, \fB__node_type\fP *__n, size_type __n_elt=1)"
.br
.ti -1c
.RI "void \fB_M_remove_bucket_begin\fP (size_type __bkt, \fB__node_type\fP *__next_n, size_type __next_bkt)"
.br
.ti -1c
.RI "void \fB_M_swap\fP (_Hashtable_base &__x)"
.br
.in -1c
.SS "Private Types"

.in +1c
.ti -1c
.RI "using \fB__bucket_alloc_traits\fP = \fBstd::allocator_traits\fP< __bucket_alloc_type >"
.br
.ti -1c
.RI "using \fB__bucket_alloc_type\fP = __alloc_rebind< __node_alloc_type, __bucket_type >"
.br
.in -1c
.SS "Private Member Functions"

.in +1c
.ti -1c
.RI "__bucket_type * \fB_M_allocate_buckets\fP (std::size_t __n)"
.br
.ti -1c
.RI "\fB__node_type\fP * \fB_M_allocate_node\fP (_Args &&\&.\&.\&. __args)"
.br
.ti -1c
.RI "void \fB_M_deallocate_buckets\fP (__bucket_type *, std::size_t __n)"
.br
.ti -1c
.RI "void \fB_M_deallocate_node\fP (\fB__node_type\fP *__n)"
.br
.ti -1c
.RI "void \fB_M_deallocate_nodes\fP (\fB__node_type\fP *__n)"
.br
.ti -1c
.RI "__node_alloc_type & \fB_M_node_allocator\fP ()"
.br
.ti -1c
.RI "const __node_alloc_type & \fB_M_node_allocator\fP () const"
.br
.in -1c
.SS "Friends"

.in +1c
.ti -1c
.RI "template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _H1a , typename _H2a , typename _Hasha , typename _RehashPolicya , typename _Traitsa , bool _Constant_iteratorsa> struct \fB__detail::_Insert\fP"
.br
.ti -1c
.RI "template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _H1a , typename _H2a , typename _Hasha , typename _RehashPolicya , typename _Traitsa > struct \fB__detail::_Insert_base\fP"
.br
.ti -1c
.RI "template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya , typename _Equala , typename _H1a , typename _H2a , typename _Hasha , typename _RehashPolicya , typename _Traitsa , bool _Unique_keysa> struct \fB__detail::_Map_base\fP"
.br
.in -1c
.SH "Detailed Description"
.PP 

.SS "template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename _Traits>
.br
class std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >"
Primary class template _Hashtable\&.
.PP
\fBTemplate Parameters:\fP
.RS 4
\fI_Value\fP CopyConstructible type\&.
.br
\fI_Key\fP CopyConstructible type\&.
.br
\fI_Alloc\fP An allocator type ([lib\&.allocator\&.requirements]) whose _Alloc::value_type is _Value\&. As a conforming extension, we allow for _Alloc::value_type != _Value\&.
.br
\fI_ExtractKey\fP Function object that takes an object of type _Value and returns a value of type _Key\&.
.br
\fI_Equal\fP 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\&.
.br
\fI_H1\fP 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()]\&.
.br
\fI_H2\fP 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)\&.
.br
\fI_Hash\fP 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\&.
.br
\fI_RehashPolicy\fP 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>)
.br
\fI_Traits\fP Compile-time class with three boolean std::integral_constant members: __cache_hash_code, __constant_iterators, __unique_keys\&.
.RE
.PP
Each _Hashtable data structure has:
.PP
.IP "\(bu" 2
_Bucket[] _M_buckets
.IP "\(bu" 2
_Hash_node_base _M_before_begin
.IP "\(bu" 2
size_type _M_bucket_count
.IP "\(bu" 2
size_type _M_element_count
.PP
.PP
with _Bucket being _Hash_node* and _Hash_node containing:
.PP
.IP "\(bu" 2
_Hash_node* _M_next
.IP "\(bu" 2
Tp _M_value
.IP "\(bu" 2
size_t _M_hash_code if cache_hash_code is true
.PP
.PP
In terms of Standard containers the hashtable is like the aggregation of:
.PP
.IP "\(bu" 2
std::forward_list<_Node> containing the elements
.IP "\(bu" 2
std::vector<std::forward_list<_Node>::iterator> representing the buckets
.PP
.PP
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\&.
.PP
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\&.
.PP
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\&.
.PP
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\&.
.PP
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\&.
.PP
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\&.
.PP
Base class templates are:
.IP "\(bu" 2
__detail::_Hashtable_base
.IP "\(bu" 2
__detail::_Map_base
.IP "\(bu" 2
__detail::_Insert
.IP "\(bu" 2
__detail::_Rehash_base
.IP "\(bu" 2
__detail::_Equality 
.PP

.PP
Definition at line 173 of file bits/hashtable\&.h\&.

.SH "Author"
.PP 
Generated automatically by Doxygen for libstdc++ from the source code\&.