.TH "std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >" 3cxx "Fri Dec 19 2014" "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, and \fBstd::__detail::_Equality< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >\fP\&.
.SS "Public Types"

.in +1c
.ti -1c
.RI "typedef _Alloc \fBallocator_type\fP"
.br
.ti -1c
.RI "using \fBconst_iterator\fP = \fB__detail::_Node_const_iterator\fP< value_type, __constant_iterators::value, __hash_cached::value >"
.br
.ti -1c
.RI "using \fBconst_local_iterator\fP = \fB__detail::_Local_const_iterator\fP< key_type, value_type, _ExtractKey, _H1, _H2, _Hash, __constant_iterators::value, __hash_cached::value >"
.br
.ti -1c
.RI "typedef _Alloc::const_pointer \fBconst_pointer\fP"
.br
.ti -1c
.RI "typedef _Alloc::const_reference \fBconst_reference\fP"
.br
.ti -1c
.RI "typedef std::ptrdiff_t \fBdifference_type\fP"
.br
.ti -1c
.RI "using \fBiterator\fP = \fB__detail::_Node_iterator\fP< value_type, __constant_iterators::value, __hash_cached::value >"
.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 = \fB__detail::_Local_iterator\fP< key_type, value_type, _ExtractKey, _H1, _H2, _Hash, __constant_iterators::value, __hash_cached::value >"
.br
.ti -1c
.RI "typedef _Alloc::pointer \fBpointer\fP"
.br
.ti -1c
.RI "typedef _Alloc::reference \fBreference\fP"
.br
.ti -1c
.RI "typedef std::size_t \fBsize_type\fP"
.br
.ti -1c
.RI "typedef _Value \fBvalue_type\fP"
.br
.in -1c
.SS "Protected Member Functions"

.in +1c
.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, __node_type *__n) const "
.br
.ti -1c
.RI "void \fB_M_swap\fP (_Hashtable_base &__x)"
.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>singleton 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_bbegin
.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 174 of file bits/hashtable\&.h\&.

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