Provided by: libstdc++-8-doc_8.3.0-23ubuntu2_all bug


       std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
       _RehashPolicy, _Traits >


       Inherits std::__detail::_Hashtable_base< _Key, _Value, _ExtractKey, _Equal, _H1, _H2,
       _Hash, _Traits >, std::__detail::_Map_base< _Key, _Value, _Alloc, _ExtractKey, _Equal,
       _H1, _H2, _Hash, _RehashPolicy, _Traits >, std::__detail::_Insert< _Key, _Value, _Alloc,
       _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >,
       std::__detail::_Rehash_base< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
       _RehashPolicy, _Traits >, std::__detail::_Equality< _Key, _Value, _Alloc, _ExtractKey,
       _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits >, and std::__detail::_Hashtable_alloc<
       __alloc_rebind< _Alloc, __detail::_Hash_node< _Value, _Traits::__hash_cached::value > > >.

   Public Types
       typedef _Alloc allocator_type
       using const_iterator = typename __hashtable_base::const_iterator
       using const_local_iterator = typename __hashtable_base::const_local_iterator
       typedef __value_alloc_traits::const_pointer const_pointer
       typedef const value_type & const_reference
       using difference_type = typename __hashtable_base::difference_type
       using iterator = typename __hashtable_base::iterator
       typedef _Equal key_equal
       typedef _Key key_type
       using local_iterator = typename __hashtable_base::local_iterator
       typedef __value_alloc_traits::pointer pointer
       typedef value_type & reference
       using size_type = typename __hashtable_base::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 &&) noexcept
       _Hashtable (const _Hashtable &, const allocator_type &)
       _Hashtable (_Hashtable &&, const allocator_type &)
       _Hashtable (const allocator_type &__a)
       _Hashtable (size_type __n, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(),
           const allocator_type &__a=allocator_type())
       template<typename _InputIterator > _Hashtable (_InputIterator __f, _InputIterator __l,
           size_type __n=0, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const
           allocator_type &__a=allocator_type())
       _Hashtable (initializer_list< value_type > __l, size_type __n=0, const _H1 &__hf=_H1(),
           const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
       const _RehashPolicy & __rehash_policy () const
       void __rehash_policy (const _RehashPolicy &__pol)
       template<typename... _Args> auto _M_emplace (std::true_type, _Args &&... __args) -> pair<
           iterator, bool >
       template<typename... _Args> auto _M_emplace (const_iterator __hint, std::false_type, _Args
           &&... __args) -> iterator
       template<typename _Arg , typename _NodeGenerator > auto _M_insert (_Arg &&__v, const
           _NodeGenerator &__node_gen, true_type, size_type __n_elt) -> pair< iterator, bool >
       template<typename _Arg , typename _NodeGenerator > auto _M_insert (const_iterator __hint,
           _Arg &&__v, const _NodeGenerator &__node_gen, false_type) -> iterator
       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> __ireturn_type emplace (_Args &&... __args)
       template<typename... _Args> iterator emplace_hint (const_iterator __hint, _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 &__k)
       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
       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) noexcept(__node_alloc_traits::_S_nothrow_move()
           &&is_nothrow_move_assignable< _H1 >::value &&is_nothrow_move_assignable< _Equal
       _Hashtable & operator= (initializer_list< value_type > __l)
       void rehash (size_type __n)
       size_type size () const noexcept
       void swap (_Hashtable &) noexcept(__and_< __is_nothrow_swappable< _H1 >,
           __is_nothrow_swappable< _Equal >>::value)

   Protected Member Functions
       size_type _M_bucket_index (__node_type *__n) const noexcept
       size_type _M_bucket_index (const key_type &__k, __hash_code __c) const
       template<typename... _Args> std::pair< iterator, bool > _M_emplace (std::true_type, _Args
           &&... __args)
       template<typename... _Args> iterator _M_emplace (std::false_type __uk, _Args &&... __args)
       template<typename... _Args> iterator _M_emplace (const_iterator, std::true_type __uk,
           _Args &&... __args)
       template<typename... _Args> iterator _M_emplace (const_iterator, std::false_type, _Args
           &&... __args)
       const _Equal & _M_eq () const
       _Equal & _M_eq ()
       bool _M_equals (const _Key &__k, __hash_code __c, __node_type *__n) const
       size_type _M_erase (std::true_type, const key_type &)
       size_type _M_erase (std::false_type, const key_type &)
       iterator _M_erase (size_type __bkt, __node_base *__prev_n, __node_type *__n)
       __node_base * _M_find_before_node (size_type, const key_type &, __hash_code) const
       __node_type * _M_find_node (size_type __bkt, const key_type &__key, __hash_code __c) const
       __node_base * _M_get_previous_node (size_type __bkt, __node_base *__n)
       template<typename _Arg , typename _NodeGenerator > std::pair< iterator, bool > _M_insert
           (_Arg &&, const _NodeGenerator &, true_type, size_type=1)
       template<typename _Arg , typename _NodeGenerator > iterator _M_insert (_Arg &&__arg, const
           _NodeGenerator &__node_gen, false_type __uk)
       template<typename _Arg , typename _NodeGenerator > iterator _M_insert (const_iterator,
           _Arg &&__arg, const _NodeGenerator &__node_gen, true_type __uk)
       template<typename _Arg , typename _NodeGenerator > iterator _M_insert (const_iterator,
           _Arg &&, const _NodeGenerator &, false_type)
       void _M_insert_bucket_begin (size_type, __node_type *)
       iterator _M_insert_multi_node (__node_type *__hint, __hash_code __code, __node_type *__n)
       iterator _M_insert_unique_node (size_type __bkt, __hash_code __code, __node_type *__n,
           size_type __n_elt=1)
       void _M_remove_bucket_begin (size_type __bkt, __node_type *__next_n, size_type __next_bkt)
       void _M_swap (_Hashtable_base &__x)

   Private Types
       using __bucket_alloc_traits = std::allocator_traits< __bucket_alloc_type >
       using __bucket_alloc_type = __alloc_rebind< __node_alloc_type, __bucket_type >

   Private Member Functions
       __bucket_type * _M_allocate_buckets (std::size_t __n)
       __node_type * _M_allocate_node (_Args &&... __args)
       void _M_deallocate_buckets (__bucket_type *, std::size_t __n)
       void _M_deallocate_node (__node_type *__n)
       void _M_deallocate_nodes (__node_type *__n)
       __node_alloc_type & _M_node_allocator ()
       const __node_alloc_type & _M_node_allocator () const

       template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya ,
           typename _Equala , typename _H1a , typename _H2a , typename _Hasha , typename
           _RehashPolicya , typename _Traitsa , bool _Constant_iteratorsa> struct
       template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya ,
           typename _Equala , typename _H1a , typename _H2a , typename _Hasha , typename
           _RehashPolicya , typename _Traitsa > struct __detail::_Insert_base
       template<typename _Keya , typename _Valuea , typename _Alloca , typename _ExtractKeya ,
           typename _Equala , typename _H1a , typename _H2a , typename _Hasha , typename
           _RehashPolicya , typename _Traitsa , bool _Unique_keysa> struct __detail::_Map_base

Detailed Description

   template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename
       _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename
       class std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
       _RehashPolicy, _Traits >" Primary class template _Hashtable.

       Template Parameters:
           _Value CopyConstructible type.
           _Key CopyConstructible type.
           _Alloc An allocator type ([lib.allocator.requirements]) whose _Alloc::value_type is
           _Value. As a conforming extension, we allow for _Alloc::value_type != _Value.
           _ExtractKey Function object that takes an object of type _Value and returns a value of
           type _Key.
           _Equal 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.
           _H1 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,
           _H2 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).
           _Hash 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.
           _RehashPolicy 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,
           _Traits Compile-time class with three boolean std::integral_constant members:
           __cache_hash_code, __constant_iterators, __unique_keys.

       Each _Hashtable data structure 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::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.

       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 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 static assertion.

       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

       Base class templates are:

       · __detail::_Hashtable_base

       · __detail::_Map_base

       · __detail::_Insert

       · __detail::_Rehash_base

       · __detail::_Equality

       Definition at line 173 of file bits/hashtable.h.


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

ble<c+Key, _Value, _Alloc, _ExtractKey, TEqual, 8H1,19H2, _Hash, _RehashPolicy, _Traits >(3cxx)