libstdc++
|
Here's _Hashtable data structure, each _Hashtable has:
with _Bucket being _Hash_node* and _Hash_node constaining:
In terms of Standard containers the hastable is like the aggregation of:
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 147 of file bits/hashtable.h.