Zen

Translation

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:
138/5600 · 560

Sign in to save translations.

English Chinese (Simplified Han script) Actions
[#structures] = Data Structures
[#structures]= 数据结构
:idprefix: structures_
:idprefix: structures_
Closed-addressing Containers
闭寻址容器
Boost.Unordered sports one of the fastest implementations of closed addressing, also commonly known as https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[separate chaining]. An example figure representing the data structure is below:
Boost.Unordered 提供了速度最快的闭寻址实现之一，该结构通常被称为 https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[分离链接法] 。其数据结构示例如下：
image::bucket-groups.png[align=center]
image::bucket-groups.png[align=center]
An array of "buckets" is allocated and each bucket in turn points to its own individual linked list. This makes meeting the standard requirements of bucket iteration straight-forward. Unfortunately, iteration of the entire container is often times slow using this layout as each bucket must be examined for occupancy, yielding a time complexity of `O(bucket_count() + size())` when the standard requires complexity to be `O(size())`.
系统分配一个"桶"数组，其中每个桶分别指向其专属的链表。这种结构使得桶迭代能直接满足标准要求。但采用此布局进行整体容器迭代通常较慢，因为需检查每个桶的占用状态，其时间复杂度为 `O(bucket++_++count() {plus} size())` ，而标准要求复杂度应为 `O(size())` 。
Canonical standard implementations will wind up looking like the diagram below:
典型的标准库实现最终会形成如下图所示的结构：
image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]
image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]
It's worth noting that this approach is only used by pass:[libc++] and pass:[libstdc++]; the MSVC Dinkumware implementation uses a different one. A more detailed analysis of the standard containers can be found http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[here].
值得注意的是，这种方法仅被 pass:[libc++] 和 pass:[libstdc++] 所采用；MSVC 的 Dinkumware 实现则使用了不同的方法。关于标准容器的更详细分析可参见 http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[此处]。
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:
这种非常规数据结构通过将所有节点连成单向链表来实现高效全局迭代。需注意：桶指向其元素起始节点的__前驱节点__，这样设计的目的是在保持高效元素删除的同时，无需引入双向链表。但这种数据结构不可避免地带来了额外的间接访问开销。例如，要访问某个桶的第一个元素，必须执行类似以下操作：
```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 // ... } ```
```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 // ... } ```
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 // ... } ```
使用简单的桶组布局，只需执行以下操作：```c++auto const idx = get_bucket_idx(hash_function(key));node* n = buckets[idx]; // 第一次加载if (n) { value_type const& v = *n; // 第二次加载 // ...}```
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:
在实际使用中，额外的间接层会对 `insert`、`find` 和 `erase` 等常见操作的性能产生显著影响。但为了保持容器的迭代速度，Boost.Unordered 引入了一种新颖的数据结构——“桶组”。桶组是桶数组的一个固定宽度的子区间视图。它包含一个位掩码（类型为 `std::size_t`），用于跟踪桶的占用情况，并包含两个指针，以便与非空组形成双向链表。下面是一个示例图：
image::fca.png[align=center]
image::fca.png[align=center]
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.
因此，容器范围内的迭代转变为遍历非空的桶组（这是一个具有常数时间复杂度的操作），从而将时间复杂度降回 `O(size())`。总体而言，一个桶组的大小仅为 4 个字，它覆盖 `sizeof(std::size_t) * CHAR_BIT` 个桶，这意味着在所有常见实现中，每个桶由桶组引入的空间开销仅为 4 位。
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].
关于 Boost.Unordered 闭地址实现的更详细描述，请参阅 https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[外部文章]。有关实现原理的更多信息，请阅读 xref:rationale.adoc#rationale_closed_addressing_containers[相应章节]。
Open-addressing Containers
开放寻址容器
The diagram shows the basic internal layout of `boost::unordered_flat_set`/`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`.
该图展示了 `boost::unordered_flat_set`/`unordered_node_set` 和 `boost::unordered_flat_map`/`unordered_node_map` 的基本内部布局。
image::foa.png[align=center]
image::foa.png[align=center]
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.
与所有开放寻址容器一样，元素（对于 `boost::unordered++_++node++_++set` 和 `boost::unordered++_++node++_++map`则是元素节点的指针）直接存储在桶数组中。 该数组在逻辑上被划分为 2^_n_^个组，每组包含 15个元素。 除桶数组外，还存在一个关联的__元数据数组__，其中包含 2^_n_^ 个 16 字节的字。
image::foa-metadata.png[align=center]
image::foa-metadata.png[align=center]
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:
一个元数据字被划分为 15 个 _h_~_i_~ 字节（每个字节对应一个关联的桶），以及一个 _溢出字节_（图中标记为 _ofw_）。_h_~_i_~ 的值计算方式如下：
- 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.
- 0 表示对应的桶为空。
- 1 用于编码一种特殊的空桶，称为 _哨位桶_，在容器被完全遍历时内部用于停止迭代。
- 如果桶被占用，则存储从元素哈希值中获得的 _缩减哈希值_。
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:
当查找一个哈希值为 _h_ 的元素时，可以使用诸如 https://en.wikipedia.org/wiki/SSE2[SSE2] 和 https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] 等 SIMD 技术，仅需少量 CPU 指令即可快速检查完整的元数据字，并在全部 15 个桶中寻找 _h_ 的缩减值：不匹配的桶可以迅速丢弃，而那些缩减哈希值匹配的桶则需要通过与对应元素的完整比较来进行检查。如果未找到目标元素，则检查溢出字节。
- 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.
- 若位置 _h_ mod 8 的比特位为零，则查找终止（确认元素不存在）。 元素不存在）。 - 若该比特位为1（表示该组已__溢出__），则通过 https://en.wikipedia.org/wiki/Quadratic_probing[_二次探查法_] 检查后续组，并重复此过程。
English Chinese (Simplified Han script) Actions
image::foa-metadata-interleaving.png[align=center]
image::foa-metadata-interleaving.png[align=center]
The value of the insertion counter for the initial group in the probe
探测起始组的插入计数器值
Lookup is as described above. If lookup finds no equivalent element,
查找过程如上所述。如果查找未找到等效元素，
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 // ... } ```
使用简单的桶组布局，只需执行以下操作：```c++auto const idx = get_bucket_idx(hash_function(key));node* n = buckets[idx]; // 第一次加载if (n) { value_type const& v = *n; // 第二次加载 // ...}```
image::fca.png[align=center]
image::fca.png[align=center]
image::foa-metadata.png[align=center]
image::foa-metadata.png[align=center]
Concurrent Containers
并发容器
When an available slot is located, it is preemptively occupied (its
当定位到一个可用槽位时，该槽位会被预先占用（其
For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].
如需了解实现原理的更多内容，请参阅 xref:rationale.adoc#rationale_concurrent_containers [对应章节]。
Boost.Unordered sports one of the fastest implementations of closed addressing, also commonly known as https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[separate chaining]. An example figure representing the data structure is below:
Boost.Unordered 提供了速度最快的闭寻址实现之一，该结构通常被称为 https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[分离链接法] 。其数据结构示例如下：
image::bucket-groups.png[align=center]
image::bucket-groups.png[align=center]
An array of "buckets" is allocated and each bucket in turn points to its own individual linked list. This makes meeting the standard requirements of bucket iteration straight-forward. Unfortunately, iteration of the entire container is often times slow using this layout as each bucket must be examined for occupancy, yielding a time complexity of `O(bucket_count() + size())` when the standard requires complexity to be `O(size())`.
系统分配一个"桶"数组，其中每个桶分别指向其专属的链表。这种结构使得桶迭代能直接满足标准要求。但采用此布局进行整体容器迭代通常较慢，因为需检查每个桶的占用状态，其时间复杂度为 `O(bucket++_++count() {plus} size())` ，而标准要求复杂度应为 `O(size())` 。
Canonical standard implementations will wind up looking like the diagram below:
典型的标准库实现最终会形成如下图所示的结构：
image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]
image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]
It's worth noting that this approach is only used by pass:[libc++] and pass:[libstdc++]; the MSVC Dinkumware implementation uses a different one. A more detailed analysis of the standard containers can be found http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[here].
值得注意的是，这种方法仅被 pass:[libc++] 和 pass:[libstdc++] 所采用；MSVC 的 Dinkumware 实现则使用了不同的方法。关于标准容器的更详细分析可参见 http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[此处]。
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:
这种非常规数据结构通过将所有节点连成单向链表来实现高效全局迭代。需注意：桶指向其元素起始节点的__前驱节点__，这样设计的目的是在保持高效元素删除的同时，无需引入双向链表。但这种数据结构不可避免地带来了额外的间接访问开销。例如，要访问某个桶的第一个元素，必须执行类似以下操作：
```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 // ... } ```
```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 // ... } ```
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:
在实际使用中，额外的间接层会对 `insert`、`find` 和 `erase` 等常见操作的性能产生显著影响。但为了保持容器的迭代速度，Boost.Unordered 引入了一种新颖的数据结构——“桶组”。桶组是桶数组的一个固定宽度的子区间视图。它包含一个位掩码（类型为 `std::size_t`），用于跟踪桶的占用情况，并包含两个指针，以便与非空组形成双向链表。下面是一个示例图：
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.
因此，容器范围内的迭代转变为遍历非空的桶组（这是一个具有常数时间复杂度的操作），从而将时间复杂度降回 `O(size())`。总体而言，一个桶组的大小仅为 4 个字，它覆盖 `sizeof(std::size_t) * CHAR_BIT` 个桶，这意味着在所有常见实现中，每个桶由桶组引入的空间开销仅为 4 位。
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].
关于 Boost.Unordered 闭地址实现的更详细描述，请参阅 https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[外部文章]。有关实现原理的更多信息，请阅读 xref:rationale.adoc#rationale_closed_addressing_containers[相应章节]。
Open-addressing Containers
开放寻址容器
The diagram shows the basic internal layout of `boost::unordered_flat_set`/`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`.
该图展示了 `boost::unordered_flat_set`/`unordered_node_set` 和 `boost::unordered_flat_map`/`unordered_node_map` 的基本内部布局。
image::foa.png[align=center]
image::foa.png[align=center]
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.
与所有开放寻址容器一样，元素（对于 `boost::unordered++_++node++_++set` 和 `boost::unordered++_++node++_++map`则是元素节点的指针）直接存储在桶数组中。 该数组在逻辑上被划分为 2^_n_^个组，每组包含 15个元素。 除桶数组外，还存在一个关联的__元数据数组__，其中包含 2^_n_^ 个 16 字节的字。
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:
一个元数据字被划分为 15 个 _h_~_i_~ 字节（每个字节对应一个关联的桶），以及一个 _溢出字节_（图中标记为 _ofw_）。_h_~_i_~ 的值计算方式如下：
- 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.
- 0 表示对应的桶为空。
- 1 用于编码一种特殊的空桶，称为 _哨位桶_，在容器被完全遍历时内部用于停止迭代。
- 如果桶被占用，则存储从元素哈希值中获得的 _缩减哈希值_。
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:
当查找一个哈希值为 _h_ 的元素时，可以使用诸如 https://en.wikipedia.org/wiki/SSE2[SSE2] 和 https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] 等 SIMD 技术，仅需少量 CPU 指令即可快速检查完整的元数据字，并在全部 15 个桶中寻找 _h_ 的缩减值：不匹配的桶可以迅速丢弃，而那些缩减哈希值匹配的桶则需要通过与对应元素的完整比较来进行检查。如果未找到目标元素，则检查溢出字节。
- 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.
- 若位置 _h_ mod 8 的比特位为零，则查找终止（确认元素不存在）。 元素不存在）。 - 若该比特位为1（表示该组已__溢出__），则通过 https://en.wikipedia.org/wiki/Quadratic_probing[_二次探查法_] 检查后续组，并重复此过程。
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.
插入操作的算法逻辑类似：通过 SIMD 技术定位空桶，当遍历到已满的组时，会将其对应的溢出位设置为 1。
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.
在不支持 SIMD 的架构中，逻辑布局保持不变，但元数据字采用一种称为 _位交错_ 的技术进行编码：这种布局允许我们仅使用标准算术和逻辑运算，以相当不错的性能来模拟 SIMD。

Loading…

User avatar admin

Translation uploaded
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:
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:这种非常规数据结构通过将所有节点连成单向链表来实现高效全局迭代。需注意：桶指向其元素起始节点的__前驱节点__，这样设计的目的是在保持高效元素删除的同时，无需引入双向链表。但这种数据结构不可避免地带来了额外的间接访问开销。例如，要访问某个桶的第一个元素，必须执行类似以下操作：
06/05/2026
User avatar admin

String added in the repository
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:
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:
06/05/2026
Browse all string changes

Glossary

English Chinese (Simplified Han script)
No related strings found in the glossary.

String information

Flags
safe-html, strict-same
Unit identifier
52261
Source string location
:32
String age
06/05/2026
Last updated
06/06/2026
Source string age
06/05/2026
Translation file AsciiDoc file
doc/modules/ROOT/pages/structures_zh_Hans.adoc, string 10