.TH "std::_Hashtable< _Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys >" 3cxx "Sun Jan 6 2013" "libstdc++" \" -*- nroff -*-
.ad l
.nh
.SH NAME
std::_Hashtable< _Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys > \- 
.SH SYNOPSIS
.br
.PP
.PP
Inherits std::__detail::_Rehash_base< _RehashPolicy, _Hashtable >, std::__detail::_Hashtable_base< _Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, __cache_hash_code >, std::__detail::_Map_base< _Key, _Value, _Ex, __unique, _Hashtable >, and _Equality_base< _ExtractKey, __unique_keys, _Hashtable< _Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys > >\&.
.SS "Public Types"

.in +1c
.ti -1c
.RI "typedef _Allocator \fBallocator_type\fP"
.br
.ti -1c
.RI "typedef 
.br
__detail::_Node_const_iterator
.br
< value_type, 
.br
__constant_iterators, 
.br
__cache_hash_code > \fBconst_iterator\fP"
.br
.ti -1c
.RI "typedef 
.br
__detail::_Local_const_iterator
.br
< key_type, value_type, 
.br
_ExtractKey, _H1, _H2, _Hash, 
.br
__constant_iterators, 
.br
__cache_hash_code > \fBconst_local_iterator\fP"
.br
.ti -1c
.RI "typedef _Allocator::const_pointer \fBconst_pointer\fP"
.br
.ti -1c
.RI "typedef _Allocator::const_reference \fBconst_reference\fP"
.br
.ti -1c
.RI "typedef std::ptrdiff_t \fBdifference_type\fP"
.br
.ti -1c
.RI "typedef 
.br
__detail::_Node_iterator
.br
< value_type, 
.br
__constant_iterators, 
.br
__cache_hash_code > \fBiterator\fP"
.br
.ti -1c
.RI "typedef _Equal \fBkey_equal\fP"
.br
.ti -1c
.RI "typedef _Key \fBkey_type\fP"
.br
.ti -1c
.RI "typedef 
.br
__detail::_Local_iterator
.br
< key_type, value_type, 
.br
_ExtractKey, _H1, _H2, _Hash, 
.br
__constant_iterators, 
.br
__cache_hash_code > \fBlocal_iterator\fP"
.br
.ti -1c
.RI "typedef _Allocator::pointer \fBpointer\fP"
.br
.ti -1c
.RI "typedef _Allocator::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 "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 &&)"
.br
.ti -1c
.RI "const _RehashPolicy & \fB__rehash_policy\fP () const "
.br
.ti -1c
.RI "void \fB__rehash_policy\fP (const _RehashPolicy &)"
.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> _Insert_Return_Type \fBemplace\fP (_Args &&\&.\&.\&.__args)"
.br
.ti -1c
.RI "template<typename\&.\&.\&. _Args> iterator \fBemplace_hint\fP (const_iterator, _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, 
.br
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 &)"
.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 "_Insert_Return_Type \fBinsert\fP (const value_type &__v)"
.br
.ti -1c
.RI "iterator \fBinsert\fP (const_iterator, const value_type &__v)"
.br
.ti -1c
.RI "template<typename _Pair , typename  = typename std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,			      std::is_constructible<value_type,						    _Pair&&>>::value>::type> _Insert_Return_Type \fBinsert\fP (_Pair &&__v)"
.br
.ti -1c
.RI "template<typename _Pair , typename  = typename std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,			      std::is_constructible<value_type,						    _Pair&&>>::value>::type> iterator \fBinsert\fP (const_iterator, _Pair &&__v)"
.br
.ti -1c
.RI "template<typename _InputIterator > void \fBinsert\fP (_InputIterator __first, _InputIterator __last)"
.br
.ti -1c
.RI "void \fBinsert\fP (\fBinitializer_list\fP< value_type > __l)"
.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)"
.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 &)"
.br
.in -1c
.SS "Protected Types"

.in +1c
.ti -1c
.RI "typedef _HCBase::_Hash_code_type \fB_Hash_code_type\fP"
.br
.in -1c
.SS "Protected Member Functions"

.in +1c
.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, _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_type __c, _Hash_node< _Value, __cache_hash_code > *__n) const "
.br
.ti -1c
.RI "template<typename _Arg > \fBstd::pair\fP< iterator, bool > \fB_M_insert\fP (_Arg &&, \fBstd::true_type\fP)"
.br
.ti -1c
.RI "template<typename _Arg > iterator \fB_M_insert\fP (_Arg &&, \fBstd::false_type\fP)"
.br
.ti -1c
.RI "void \fB_M_swap\fP (_Hashtable_base &__x)"
.br
.in -1c
.SS "Friends"

.in +1c
.ti -1c
.RI "template<typename _Key2 , typename _Value2 , typename _Ex2 , bool __unique2, typename _Hashtable2 > struct \fB__detail::_Map_base\fP"
.br
.in -1c
.SH "Detailed Description"
.PP 

.SS "template<typename _Key, typename _Value, typename _Allocator, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, bool __cache_hash_code, bool __constant_iterators, bool __unique_keys>class std::_Hashtable< _Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys >"
Here's \fB_Hashtable\fP data structure, each \fB_Hashtable\fP has:
.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 constaining:
.IP "\(bu" 2
_Hash_node* _M_next
.IP "\(bu" 2
Tp _M_value
.IP "\(bu" 2
size_t _M_code if cache_hash_code is true
.PP
.PP
In terms of Standard containers the hastable is like the aggregation of:
.IP "\(bu" 2
std::forward_list<_Node> containing the elements
.IP "\(bu" 2
\fBstd::vector\fP<std::forward_list<_Node>::iterator> representing the buckets
.PP
.PP
The non-empty buckets contain the node before the first bucket node\&. This design allow to implement something like a \fBstd::forward_list::insert_after\fP on container insertion and \fBstd::forward_list::erase_after\fP on container erase calls\&. _M_before_begin is equivalent to std::foward_list::before_begin\&. Empty buckets are containing nullptr\&. Note that one of the non-empty bucket contains &_M_before_begin which is not a derefenrenceable node so the node pointers in buckets shall never be derefenrenced, only its next node can be\&.
.PP
Walk through a bucket nodes require a check on the hash code to see if the node is still in the bucket\&. Such a design impose a quite efficient hash functor and is one of the reasons it is highly advise 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 element hash code and thanks to it find the bucket index\&. If the element must be inserted on 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 impose to use the hash functor to get the index of the bucket to update\&. For this reason, when __cache_hash_code is set to false, there is a static assertion that the hash functor cannot throw\&. 
.PP
Definition at line 148 of file bits/hashtable\&.h\&.

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