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 _Equality_base< _ExtractKey, __unique_keys, _Hashtable< _Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys > >.

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 &) 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 constaining:

•

_Hash_node* _M_next

•

Tp _M_value

•

size_t _M_code if cache_hash_code is true

In terms of Standard containers the hastable 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 bucket node. This design allow 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 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. 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. 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 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. 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. Definition at line 148 of file bits/hashtable.h.

Author¶

Generated automatically by Doxygen for libstdc++ from the source code.