STD::_HASHTABLE(3cxx)

📦
version 10.5.0 · 6 versions
, in ubuntu noble

💖 NAME 💖

Hiii bestie, welcome to the (3cxx) page for std::_Hashtable< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits > ✨ She's the secret main-character engine hiding under all your unordered_* containers, and she has so many template parameters. It's giving "I contain multitudes" and honestly? She does. This is part 1, and we're going through every single thing, no skips. 🎀

🌸 SYNOPSIS 🌸

First, the include, because obviously:

#include <hashtable.h>

And she does not come alone — she inherits from a whole friend group. All of them, in order:

  • 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, _Unique_keys >
  • std::__detail::_Insert< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, _Constant_iterators >
  • std::__detail::_Rehash_base< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, typename >
  • std::__detail::_Equality< _Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, _Unique_keys >
  • std::__detail::_Hashtable_alloc< __alloc_rebind< _Alloc, __detail::_Hash_node< _Value, _Traits::__hash_cached::value > > >
  • and std::_Enable_default_constructor< _Switch, _Tag >

That's her lineage. Ancestry dot com could never. 🦋

🫶 Public Types 🫶

Her little type aliases, every single one, in order:

  • typedef _Alloc allocator_type — the allocator, the one holding the memory bag 💅
  • using const_iterator = typename __hashtable_base::const_iterator — the const iterator, freshly borrowed from __hashtable_base
  • using const_local_iterator = typename __hashtable_base::const_local_iterator — const version of the local (per-bucket) iterator
  • typedef __value_alloc_traits::const_pointer const_pointer — a const pointer, straight from __value_alloc_traits
  • typedef const value_type & const_reference — a const reference to a value_type
  • using difference_type = typename __hashtable_base::difference_type — the difference type, inherited vibe
  • using iterator = typename __hashtable_base::iterator — the iterator, also from __hashtable_base
  • typedef _Equal key_equal — her key-equality functor type
  • typedef _Key key_type — the key type, yes it's literally _Key
  • using local_iterator = typename __hashtable_base::local_iterator — the local iterator (the bucket-specific one)
  • typedef __value_alloc_traits::pointer pointer — a pointer, from __value_alloc_traits
  • typedef value_type & reference — a plain reference to a value_type
  • using size_type = typename __hashtable_base::size_type — the size type, again from __hashtable_base
  • typedef _Value value_type — the value type, aka _Value

Periodt. That's the whole type roster. 💜

👑 Public Member Functions 👑

Okay this is the big one, and yes we're doing all of them. Buckle up bestie, grab a strawberry 🍓.

The constructors:

  • _Hashtable (_Hashtable &&__ht) noexcept(_S_nothrow_move()) — move constructor, and she's noexcept exactly when _S_nothrow_move() says so
  • _Hashtable (_Hashtable &&__ht, const allocator_type &__a) noexcept(_S_nothrow_move< __node_alloc_traits::_S_always_equal()>()) — move constructor that also takes an allocator, with her own conditional noexcept
  • template<typename _InputIterator > _Hashtable (_InputIterator __f, _InputIterator __l, size_type __bkt_count_hint=0, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type()) — iterator-range constructor with bucket hint, hash, equality and allocator all defaulted
  • template<typename _InputIterator > _Hashtable (_InputIterator __first, _InputIterator __last, size_type __bkt_count_hint, const _H1 &, const _H2 &, const _Hash &, const _Equal &, const _ExtractKey &, const allocator_type &) — the full-drip range constructor where nothing is defaulted
  • _Hashtable (const _Hashtable &) — copy constructor, classic
  • _Hashtable (const _Hashtable &, const allocator_type &) — copy constructor that also takes an allocator
  • _Hashtable (const allocator_type &__a) — allocator-only constructor
  • _Hashtable (initializer_list< value_type > __l, size_type __bkt_count_hint=0, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type()) — the initializer_list constructor, with bucket hint + hash + equality + allocator all defaulted
  • _Hashtable (size_type __bkt_count_hint, const _H1 &, const _H2 &, const _Hash &, const _Equal &, const _ExtractKey &, const allocator_type &) — bucket hint plus every functor, fully specified
  • _Hashtable (size_type __bkt_count_hint, const _H1 &__hf=_H1(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type()) — bucket hint with the defaulted hash, equality and allocator

Rehash policy access:

  • const _RehashPolicy & __rehash_policy () const — hands you back the rehash policy, const-style
  • void __rehash_policy (const _RehashPolicy &__pol) — sets the rehash policy from __pol

Internal insert/emplace machinery (public-flavored):

  • template<typename... _Args> auto _M_emplace (const_iterator __hint, false_type, _Args &&... __args) -> iterator — emplace with a hint and a false_type, returns an iterator
  • template<typename... _Args> auto _M_emplace (true_type, _Args &&... __args) -> pair< iterator, bool > — emplace with a true_type, returns a pair< iterator, bool >
  • template<typename _Arg , typename _NodeGenerator > auto _M_insert (_Arg &&__v, const _NodeGenerator &__node_gen, true_type, size_type __n_elt) -> pair< iterator, bool > — insert with a node generator, a true_type and an element count, returns pair< iterator, bool >
  • template<typename _Arg , typename _NodeGenerator > auto _M_insert (const_iterator __hint, _Arg &&__v, const _NodeGenerator &__node_gen, false_type) -> iterator — hinted insert with node generator and false_type, returns iterator

Iterating (all the begins):

  • const_iterator begin () const noexcept — const begin, noexcept
  • iterator begin () noexcept — non-const begin, noexcept
  • local_iterator begin (size_type __bkt) — begin for a specific bucket __bkt
  • const_local_iterator begin (size_type __bkt) const — const begin for bucket __bkt

Bucket business:

  • size_type bucket (const key_type &__k) const — which bucket does key __k live in?
  • size_type bucket_count () const noexcept — how many buckets total, noexcept
  • size_type bucket_size (size_type __bkt) const — how big is bucket __bkt

Const-iteration starters:

  • const_iterator cbegin () const noexcept — const begin, the c version
  • const_local_iterator cbegin (size_type __bkt) const — const local begin for bucket __bkt
  • const_iterator cend () const noexcept — const end, noexcept
  • const_local_iterator cend (size_type __bkt) const — const local end for bucket __bkt

Clearing, counting, emplacing:

  • void clear () noexcept — wipe it all, noexcept
  • size_type count (const key_type &__k) const — how many times does __k show up
  • template<typename... _Args> __ireturn_type emplace (_Args &&... __args) — emplace, returns __ireturn_type
  • template<typename... _Args> iterator emplace_hint (const_iterator __hint, _Args &&... __args) — emplace but with a __hint, returns an iterator
  • bool empty () const noexcept — is she empty, noexcept

The ends:

  • const_iterator end () const noexcept — const end, noexcept
  • iterator end () noexcept — non-const end, noexcept
  • local_iterator end (size_type __bkt) — end for bucket __bkt
  • const_local_iterator end (size_type __bkt) const — const end for bucket __bkt

Lookups and ranges:

  • std::pair< iterator, iterator > equal_range (const key_type &__k) — the range where __k lives, non-const
  • std::pair< const_iterator, const_iterator > equal_range (const key_type &__k) const — the const version of that range

Erasing (four whole flavors):

  • size_type erase (const key_type &__k) — erase by key, tells you how many went bye
  • iterator erase (const_iterator) — erase by const iterator, returns an iterator
  • iterator erase (const_iterator, const_iterator) — erase a whole const-iterator range
  • iterator erase (iterator __it) — erase by iterator __it

Finding + properties:

  • iterator find (const key_type &__k) — find __k, non-const
  • const_iterator find (const key_type &__k) const — find __k, const
  • allocator_type get_allocator () const noexcept — hand over the allocator, noexcept
  • key_equal key_eq () const — hand over the key-equality functor
  • float load_factor () const noexcept — the load factor as a float, noexcept
  • size_type max_bucket_count () const noexcept — the max bucket count, noexcept
  • size_type max_size () const noexcept — the max size, noexcept

Assignment operators:

  • _Hashtable & operator= (_Hashtable &&__ht) noexcept(__node_alloc_traits::_S_nothrow_move() &&is_nothrow_move_assignable< _H1 >::value &&is_nothrow_move_assignable< _Equal >::value) — move assignment, noexcept under that exact condition
  • _Hashtable & operator= (const _Hashtable &__ht) — copy assignment from __ht
  • _Hashtable & operator= (initializer_list< value_type > __l) — assign from an initializer_list __l

Resizing + the rest:

  • void rehash (size_type __bkt_count) — rehash into __bkt_count buckets
  • size_type size () const noexcept — how many elements, noexcept
  • void swap (_Hashtable &) noexcept(__and_< __is_nothrow_swappable< _H1 >, __is_nothrow_swappable< _Equal > >::value) — swap, noexcept exactly when __and_< __is_nothrow_swappable< _H1 >, __is_nothrow_swappable< _Equal > >::value holds

🙈 Protected Member Functions 🙈

These are the behind-the-scenes girls — protected, so they're for the family only:

  • size_type _M_bucket_index (__node_type *__n) const noexcept — bucket index from a node pointer, noexcept
  • size_type _M_bucket_index (const key_type &__k, __hash_code __c) const — bucket index from key __k and hash code __c
  • template<typename... _Args> iterator _M_emplace (const_iterator, false_type, _Args &&... __args) — protected emplace, const-iterator + false_type, returns iterator
  • template<typename... _Args> iterator _M_emplace (const_iterator, true_type __uk, _Args &&... __args) — protected emplace with const-iterator and true_type __uk
  • template<typename... _Args> iterator _M_emplace (false_type __uk, _Args &&... __args) — protected emplace with just false_type __uk
  • template<typename... _Args> std::pair< iterator, bool > _M_emplace (true_type, _Args &&... __args) — protected emplace with true_type, returns std::pair< iterator, bool >
  • const _Equal & _M_eq () const — hands back the equality functor, const
  • bool _M_equals (const _Key &__k, __hash_code __c, __node_type *__n) const — does __k (hash __c) equal node __n?
  • size_type _M_erase (false_type, const key_type &) — erase path with false_type, returns size_type
  • iterator _M_erase (size_type __bkt, __node_base *__prev_n, __node_type *__n) — erase node __n in bucket __bkt with previous node __prev_n
  • size_type _M_erase (true_type, const key_type &) — erase path with true_type, returns size_type
  • __node_base * _M_find_before_node (size_type, const key_type &, __hash_code) const — finds the node before the one you're looking for, returns __node_base *
  • __node_type * _M_find_node (size_type __bkt, const key_type &__key, __hash_code __c) const — finds the node for __key in bucket __bkt with hash __c
  • __node_base * _M_get_previous_node (size_type __bkt, __node_base *__n) — grabs the previous node of __n in bucket __bkt
  • template<typename _Arg , typename _NodeGenerator > std::pair< iterator, bool > _M_insert (_Arg &&, const _NodeGenerator &, true_type, size_type=1) — protected insert, true_type, default size_type=1, returns std::pair< iterator, bool >
  • template<typename _Arg , typename _NodeGenerator > iterator _M_insert (_Arg &&__arg, const _NodeGenerator &__node_gen, false_type __uk) — protected insert with false_type __uk, returns iterator
  • template<typename _Arg , typename _NodeGenerator > iterator _M_insert (const_iterator, _Arg &&, const _NodeGenerator &, false_type) — protected hinted insert with false_type
  • template<typename _Arg , typename _NodeGenerator > iterator _M_insert (const_iterator, _Arg &&__arg, const _NodeGenerator &__node_gen, true_type __uk) — protected hinted insert with true_type __uk
  • void _M_insert_bucket_begin (size_type, __node_type *) — inserts at the beginning of a bucket
  • iterator _M_insert_multi_node (__node_type *__hint, const key_type &__k, __hash_code __code, __node_type *__n) — the multi-key node insert, with __hint, key __k, code __code, node __n
  • iterator _M_insert_unique_node (const key_type &__k, size_type __bkt, __hash_code __code, __node_type *__n, size_type __n_elt=1) — the unique-key node insert, with __n_elt=1 by default
  • void _M_remove_bucket_begin (size_type __bkt, __node_type *__next_n, size_type __next_bkt) — removes the beginning of bucket __bkt, next node __next_n, next bucket __next_bkt
  • void _M_swap (_Hashtable_base &__x) — swaps internals with _Hashtable_base &__x

💀 Friends 💀

Her inner circle — these structs get to see her private bits:

  • 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::_Equality — friend struct __detail::_Equality
  • 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 __detail::_Insert — friend struct __detail::_Insert
  • 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 — friend 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 — friend struct __detail::_Map_base
Part 1 done, bestie — but we are not done, part 2 is loading… 💅✨

✨ Detailed Description ✨

okay bestie, buckle up, because this is the main character of the whole page 💅

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

This is the Primary class template _Hashtable. Yes, the one. The blueprint behind the scenes. 🎀

🧩 Template Parameters

  • _Value — a CopyConstructible type. It has to be copyable, no exceptions, that's the vibe. 🫶
  • _Key — also a CopyConstructible type.
  • _Alloc — an allocator type ([lib.allocator.requirements]) whose _Alloc::value_type is _Value. And here's the fun part: as a conforming extension, we allow _Alloc::value_type != _Value. Iconic of them tbh. ✨
  • _ExtractKey — a function object that takes an object of type _Value and returns a value of type _Key. It's the "so what's the key here" guy. 🔑
  • _Equal — a 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. Lowkey just a fancy == with commitment. 💜
  • _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, numeric_limits<size_t>:::max()]. Spread it out, don't be shy. 🌈
  • _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). Noted, kings. 👑
  • _Hash — the ranged hash function (Tavori and Dreizin, again, they're famous here). 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). And hear me out — if _Hash is anything other than the default, _H1 and _H2 are ignored. Periodt. 😭
  • _RehashPolicy — a policy class with three members, and all three of them govern the bucket count. So:
    • _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) decides 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, it returns make_pair(true, n), where n is the new bucket count. If not, it returns make_pair(false, <anything>). The <anything> is sending me ngl 💀
  • _Traits — a compile-time class with three boolean std::integral_constant members: __cache_hash_code, __constant_iterators, __unique_keys. Three little booleans doing the most. 🎀

🗂️ Every _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 Actual Tea (implementation notes)

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.

🚨 okay bestie listen up: 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. Do not try it. I'm serious. 🙈

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 this is one of the reasons it is highly advisable to set __cache_hash_code to true. Do it. For me. 💖

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. Like, perfectly efficient. Slay. ⭐

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. It's giving choreography. 🦋

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. The compiler will catch you. It always does. 😤

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 pattern. So close to CRTP but not quite — it's giving "we have CRTP at home". 💅

🧬 Base class templates are:

  • __detail::_Hashtable_base
  • __detail::_Map_base
  • __detail::_Insert
  • __detail::_Rehash_base
  • __detail::_Equality

👑 Author

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

and that's the whole page bestie, we ate and left no crumbs 🍓✨ this lil masterpiece lives in the libstdc++ docs, was auto-generated by Doxygen straight from the source code, and it's filed under section 3cxx — the footer itself is just that mangled libstdstd::_Hashtabl...licy, _Traits >(3cxx) title treatment, so no date to give you, sorry, the manpage didn't leave a timestamp. mwah, go set __cache_hash_code to true 💖🫶🌈

📦 where this page comes from