Provided by: libstdc++6-4.7-doc_4.7.3-12ubuntu1_all 
NAME
std::_Hashtable< _Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy,
__cache_hash_code, __constant_iterators, __unique_keys > -
SYNOPSIS
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 std::__detail::_Equality_base< _ExtractKey, __unique_keys,
_Hashtable >.
Public Types
typedef _Allocator allocator_type
typedef
__detail::_Node_const_iterator
< value_type,
__constant_iterators,
__cache_hash_code > const_iterator"
typedef
__detail::_Local_const_iterator
< key_type, value_type,
_ExtractKey, _H1, _H2, _Hash,
__constant_iterators,
__cache_hash_code > const_local_iterator"
typedef _Allocator::const_pointer const_pointer
typedef _Allocator::const_reference const_reference
typedef std::ptrdiff_t difference_type
typedef
__detail::_Node_iterator
< value_type,
__constant_iterators,
__cache_hash_code > iterator"
typedef _Equal key_equal
typedef _Key key_type
typedef
__detail::_Local_iterator
< key_type, value_type,
_ExtractKey, _H1, _H2, _Hash,
__constant_iterators,
__cache_hash_code > local_iterator"
typedef _Allocator::pointer pointer
typedef _Allocator::reference reference
typedef std::size_t size_type
typedef _Value value_type
Public Member Functions
_Hashtable (size_type __bucket_hint, const _H1 &, const _H2 &, const _Hash &, const _Equal &, const
_ExtractKey &, const allocator_type &)
template<typename _InputIterator > _Hashtable (_InputIterator __first, _InputIterator __last, size_type
__bucket_hint, const _H1 &, const _H2 &, const _Hash &, const _Equal &, const _ExtractKey &, const
allocator_type &)
_Hashtable (const _Hashtable &)
_Hashtable (_Hashtable &&)
const _RehashPolicy & __rehash_policy () const
void __rehash_policy (const _RehashPolicy &)
template<typename... _Args> _Hashtable< _Key, _Value,
_Allocator, _ExtractKey,
_Equal, _H1, _H2, _Hash,
_RehashPolicy, __chc, __cit,
__uk >::_Node * _M_allocate_node (_Args &&...__args)"
template<typename... _Args> std::pair< typename _Hashtable
< _Key, _Value, _Allocator,
_ExtractKey, _Equal, _H1, _H2,
_Hash, _RehashPolicy, __chc,
__cit, __uk >::iterator, bool > _M_emplace (std::true_type, _Args &&...__args)"
template<typename... _Args> _Hashtable< _Key, _Value,
_Allocator, _ExtractKey,
_Equal, _H1, _H2, _Hash,
_RehashPolicy, __chc, __cit,
__uk >::iterator _M_emplace (std::false_type, _Args &&...__args)"
template<typename _Arg > std::pair< typename _Hashtable
< _Key, _Value, _Allocator,
_ExtractKey, _Equal, _H1, _H2,
_Hash, _RehashPolicy, __chc,
__cit, __uk >::iterator, bool > _M_insert (_Arg &&__v, std::true_type)"
template<typename _Arg > _Hashtable< _Key, _Value,
_Allocator, _ExtractKey,
_Equal, _H1, _H2, _Hash,
_RehashPolicy, __chc, __cit,
__uk >::iterator _M_insert (_Arg &&__v, std::false_type)"
template<typename _Arg > _Hashtable< _Key, _Value,
_Allocator, _ExtractKey,
_Equal, _H1, _H2, _Hash,
_RehashPolicy, __chc, __cit,
__uk >::iterator _M_insert_bucket (_Arg &&__v, size_type __n, typename _Hashtable::_Hash_code_type
__code)"
iterator begin () noexcept
const_iterator begin () const noexcept
local_iterator begin (size_type __n)
const_local_iterator begin (size_type __n) const
size_type bucket (const key_type &__k) const
size_type bucket_count () const noexcept
size_type bucket_size (size_type __n) const
const_iterator cbegin () const noexcept
const_local_iterator cbegin (size_type __n) const
const_iterator cend () const noexcept
const_local_iterator cend (size_type __n) const
void clear () noexcept
size_type count (const key_type &__k) const
template<typename... _Args> _Insert_Return_Type emplace (_Args &&...__args)
template<typename... _Args> iterator emplace_hint (const_iterator, _Args &&...__args)
bool empty () const noexcept
iterator end () noexcept
const_iterator end () const noexcept
local_iterator end (size_type __n)
const_local_iterator end (size_type __n) const
std::pair< iterator, iterator > equal_range (const key_type &__k)
std::pair< const_iterator,
const_iterator > equal_range (const key_type &__k) const "
iterator erase (const_iterator)
iterator erase (iterator __it)
size_type erase (const key_type &)
iterator erase (const_iterator, const_iterator)
iterator find (const key_type &__k)
const_iterator find (const key_type &__k) const
allocator_type get_allocator () const noexcept
_Insert_Return_Type insert (const value_type &__v)
iterator insert (const_iterator, const value_type &__v)
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 insert (_Pair &&__v)
template<typename _Pair , typename = typename std::enable_if<__and_<integral_constant<bool,
!__constant_iterators>,
std::is_constructible<value_type, _Pair&&>>::value>::type> iterator
insert (const_iterator, _Pair &&__v)
template<typename _InputIterator > void insert (_InputIterator __first, _InputIterator __last)
void insert (initializer_list< value_type > __l)
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= (const _Hashtable &__ht)
_Hashtable & operator= (_Hashtable &&__ht)
void rehash (size_type __n)
size_type size () const noexcept
void swap (_Hashtable &)
Protected Types
typedef _HCBase::_Hash_code_type _Hash_code_type
Protected Member Functions
template<typename... _Args> std::pair< iterator, bool > _M_emplace (std::true_type, _Args &&...__args)
template<typename... _Args> iterator _M_emplace (std::false_type, _Args &&...__args)
const _Equal & _M_eq () const
_Equal & _M_eq ()
bool _M_equals (const _Key &__k, _Hash_code_type __c, _Hash_node< _Value, __cache_hash_code > *__n) const
template<typename _Arg > std::pair< iterator, bool > _M_insert (_Arg &&, std::true_type)
template<typename _Arg > iterator _M_insert (_Arg &&, std::false_type)
void _M_swap (_Hashtable_base &__x)
Friends
template<typename _Key2 , typename _Value2 , typename _Ex2 , bool __unique2, typename _Hashtable2 >
struct __detail::_Map_base
Detailed Description
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 _Hashtable data structure, each _Hashtable 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::foward_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 it 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 statied assertion.
Definition at line 149 of file bits/hashtable.h.
Author
Generated automatically by Doxygen for libstdc++ from the source code.
libstdc++ Thu Mar std::_Hashtable< _Key, ...rators, __unique_keys >(3cxx)