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.
The documentation for this class was generated from the following file:
