2. Boost Unordered Translation (zh_Hans)
3. Doc / Modules / Root / Pages / Structures (adoc)
4. English
5. Zen

10 :32
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — This unusually laid out data structure is chosen to make iteration of the entire container efficient by inter-connecting all of the nodes into a singly-linked list. One might also notice that buckets point to the node _before_ the start of the bucket's elements. This is done so that removing elements from the list can be done efficiently without introducing the need for a doubly-linked list. Unfortunately, this data structure introduces a guaranteed extra indirection. For example, to access the first element of a bucket, something like this must be done: 560/10000 · 560
11 :34
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — ```c++ auto const idx = get_bucket_idx(hash_function(key)); node* p = buckets[idx]; // first load node* n = p->next; // second load if (n && is_in_bucket(n, idx)) { value_type const& v = *n; // third load // ... } ``` 217/10000 · 217
12 :44
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — With a simple bucket group layout, this is all that must be done: ```c++ auto const idx = get_bucket_idx(hash_function(key)); node* n = buckets[idx]; // first load if (n) { value_type const& v = *n; // second load // ... } ``` 226/10000 · 226
13 :54
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In practice, the extra indirection can have a dramatic performance impact to common operations such as `insert`, `find` and `erase`. But to keep iteration of the container fast, Boost.Unordered introduces a novel data structure, a "bucket group". A bucket group is a fixed-width view of a subsection of the buckets array. It contains a bitmask (a `std::size_t`) which it uses to track occupancy of buckets and contains two pointers so that it can form a doubly-linked list with non-empty groups. An example diagram is below: 524/10000 · 524
14 :58
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::fca.png[align=center] 28/10000 · 28
15 :60
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Thus container-wide iteration is turned into traversing the non-empty bucket groups (an operation with constant time complexity) which reduces the time complexity back to `O(size())`. In total, a bucket group is only 4 words in size and it views `sizeof(std::size_t) * CHAR_BIT` buckets meaning that for all common implementations, there's only 4 bits of space overhead per bucket introduced by the bucket groups. 413/10000 · 413
16 :62
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A more detailed description of Boost.Unordered's closed-addressing implementation is given in an https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_closed_addressing_containers[corresponding section]. 327/10000 · 327
17 :68
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Open-addressing Containers 26/10000 · 26
18 :70
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The diagram shows the basic internal layout of `boost::unordered_flat_set`/`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`. 148/10000 · 148
19 :76
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::foa.png[align=center] 28/10000 · 28
20 :78
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — As with all open-addressing containers, elements (or pointers to the element nodes in the case of `boost::unordered_node_set` and `boost::unordered_node_map`) are stored directly in the bucket array. This array is logically divided into 2^_n_^ _groups_ of 15 elements each. In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^ 16-byte words. 373/10000 · 373
21 :86
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::foa-metadata.png[align=center] 37/10000 · 37
22 :88
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is: 156/10000 · 156
23 :91
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — - 0 if the corresponding bucket is empty. - 1 to encode a special empty bucket called a _sentinel_, which is used internally to stop iteration when the container has been fully traversed. - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of the element. 284/10000 · 284
24 :97
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — When looking for an element with hash value _h_, SIMD technologies such as https://en.wikipedia.org/wiki/SSE2[SSE2] and https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the 15 buckets with just a handful of CPU instructions: non-matching buckets can be readily discarded, and those whose reduced hash value matches need be inspected via full comparison with the corresponding element. If the looked-for element is not present, the overflow byte is inspected: 594/10000 · 594
25 :106
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — - If the bit in the position _h_ mod 8 is zero, lookup terminates (and the element is not present). - If the bit is set to 1 (the group has been _overflowed_), further groups are checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and the process is repeated. 291/10000 · 291
26 :112
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Insertion is algorithmically similar: empty buckets are located using SIMD, and when going past a full group its corresponding overflow bit is set to 1. 152/10000 · 152
27 :115
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In architectures without SIMD support, the logical layout stays the same, but the metadata word is codified using a technique we call _bit interleaving_: this layout allows us to emulate SIMD with reasonably good performance using only standard arithmetic and logical operations. 279/10000 · 279
28 :122
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::foa-metadata-interleaving.png[align=center] 50/10000 · 50
29 :124
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — A more detailed description of Boost.Unordered's open-addressing implementation is given in an https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_open_addresing_containers[corresponding section]. 324/10000 · 324