---
name: "std::_Hashtable"
section: "3cxx"
platform: "linux"
package: "libstdc++-10-doc"
version: "10.2.1-6"
release: "Debian 11 (Bullseye)"
platforms: ["linux"]
url: "https://new.carta.tech/std::_Hashtable"
---

# std::\_Hashtable(3cxx)

## NAME

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

## SYNOPSIS

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, \_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 \>**, 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** (**\_Hashtable** &&) noexcept\
 **\_Hashtable** (**\_Hashtable** &&, const allocator\_type &)\
 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())\
 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 &)\
 **\_Hashtable** (const **\_Hashtable** &)\
 **\_Hashtable** (const **\_Hashtable** &, const allocator\_type &)\
 **\_Hashtable** (const allocator\_type &\_\_a)\
 **\_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())\
 **\_Hashtable** (size\_type \_\_bkt\_count\_hint, const \_H1 &, const \_H2 &, const \_Hash &, const \_Equal &, const \_ExtractKey &, const allocator\_type &)\
 **\_Hashtable** (size\_type \_\_bkt\_count\_hint, 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** (const\_iterator \_\_hint, **false\_type**, \_Args &&... \_\_args) -\> iterator\
 template\<typename... \_Args\> auto **\_M\_emplace** (**true\_type**, \_Args &&... \_\_args) -\> **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 \>\
 template\<typename \_Arg , typename \_NodeGenerator \> auto **\_M\_insert** (const\_iterator \_\_hint, \_Arg &&\_\_v, const \_NodeGenerator &\_\_node\_gen, **false\_type**) -\> iterator\
 const\_iterator **begin** () const noexcept\
 iterator **begin** () noexcept\
 local\_iterator **begin** (size\_type \_\_bkt)\
 const\_local\_iterator **begin** (size\_type \_\_bkt) const\
 size\_type **bucket** (const key\_type &\_\_k) const\
 size\_type **bucket\_count** () const noexcept\
 size\_type **bucket\_size** (size\_type \_\_bkt) const\
 const\_iterator **cbegin** () const noexcept\
 const\_local\_iterator **cbegin** (size\_type \_\_bkt) const\
 const\_iterator **cend** () const noexcept\
 const\_local\_iterator **cend** (size\_type \_\_bkt) 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 &&... \_\_args)\
 bool **empty** () const noexcept\
 const\_iterator **end** () const noexcept\
 iterator **end** () noexcept\
 local\_iterator **end** (size\_type \_\_bkt)\
 const\_local\_iterator **end** (size\_type \_\_bkt) const\
 **std::pair**\< iterator, iterator \> **equal\_range** (const key\_type &\_\_k)\
 **std::pair**\< const\_iterator, const\_iterator \> **equal\_range** (const key\_type &\_\_k) const\
 size\_type **erase** (const key\_type &\_\_k)\
 iterator **erase** (const\_iterator)\
 iterator **erase** (const\_iterator, const\_iterator)\
 iterator **erase** (iterator \_\_it)\
 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=** (**\_Hashtable** &&\_\_ht) noexcept(\_\_node\_alloc\_traits::\_S\_nothrow\_move() &&**is\_nothrow\_move\_assignable**\< \_H1 \>::value &&**is\_nothrow\_move\_assignable**\< \_Equal \>::value)\
 **\_Hashtable** & **operator=** (const **\_Hashtable** &\_\_ht)\
 **\_Hashtable** & **operator=** (**initializer\_list**\< value\_type \> \_\_l)\
 void **rehash** (size\_type \_\_bkt\_count)\
 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\> iterator **\_M\_emplace** (const\_iterator, **false\_type**, \_Args &&... \_\_args)\
 template\<typename... \_Args\> iterator **\_M\_emplace** (const\_iterator, **true\_type** \_\_uk, \_Args &&... \_\_args)\
 template\<typename... \_Args\> iterator **\_M\_emplace** (**false\_type** \_\_uk, \_Args &&... \_\_args)\
 template\<typename... \_Args\> **std::pair**\< iterator, bool \> **\_M\_emplace** (**true\_type**, \_Args &&... \_\_args)\
 const \_Equal & **\_M\_eq** () const\
 bool **\_M\_equals** (const \_Key &\_\_k, \_\_hash\_code \_\_c, **\_\_node\_type** \*\_\_n) const\
 size\_type **\_M\_erase** (**false\_type**, const key\_type &)\
 iterator **\_M\_erase** (size\_type \_\_bkt, \_\_node\_base \*\_\_prev\_n, **\_\_node\_type** \*\_\_n)\
 size\_type **\_M\_erase** (**true\_type**, const key\_type &)\
 \_\_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 &&, const \_NodeGenerator &, **false\_type**)\
 template\<typename \_Arg , typename \_NodeGenerator \> iterator **\_M\_insert** (const\_iterator, \_Arg &&\_\_arg, const \_NodeGenerator &\_\_node\_gen, **true\_type** \_\_uk)\
 void **\_M\_insert\_bucket\_begin** (size\_type, **\_\_node\_type** \*)\
 iterator **\_M\_insert\_multi\_node** (**\_\_node\_type** \*\_\_hint, const key\_type &\_\_k, \_\_hash\_code \_\_code, **\_\_node\_type** \*\_\_n)\
 iterator **\_M\_insert\_unique\_node** (const key\_type &\_\_k, 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)\

### Friends

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**\
 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**\
 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 \_Traits\>

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, numeric\_limits\<size\_t\>:::max()\].\
 *\_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, \<anything\>)\
 *\_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 pattern.

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.

## Author

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