User avatar admin

Translation uploaded
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].
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].此处]。
06/05/2026
User avatar admin

Translation uploaded
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]
06/05/2026
User avatar admin

Translation uploaded
Canonical standard implementations will wind up looking like the diagram below:
Canonical standard implementations will wind up looking like the diagram below:典型的标准库实现最终会形成如下图所示的结构：
06/05/2026
User avatar admin

Translation uploaded
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())`.
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() +{plus} size())` when the standard requires complexity to be，而标准要求复杂度应为 `O(size())`. 。
06/05/2026
User avatar admin

Translation uploaded
image::bucket-groups.png[align=center]
image::bucket-groups.png[align=center]
06/05/2026
User avatar admin

Translation uploaded
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 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:提供了速度最快的闭寻址实现之一，该结构通常被称为 https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[分离链接法] 。其数据结构示例如下：
06/05/2026
User avatar admin

Translation uploaded
Closed-addressing Containers
Closed-addressing Containers闭寻址容器
06/05/2026
User avatar admin

Translation uploaded
:idprefix: structures_
:idprefix: structures_
06/05/2026
User avatar admin

Translation uploaded
[#structures] = Data Structures
[#structures] = Data Structures数据结构
06/05/2026
User avatar admin

Resource updated
The “doc/modules/ROOT/pages/structures_zh_Hans.adoc” file was changed. 06/05/2026
User avatar admin

Resource updated
File “doc/modules/ROOT/pages/structures_zh_Hans.adoc” was added. 06/05/2026
User avatar admin

String added in the repository
For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].
 
06/05/2026
User avatar admin

String added in the repository
This algorithm has very low contention both at the lookup and actual insertion phases in exchange for the possibility that computations have to be started over if some other thread interferes in the process by performing a succesful insertion beginning at the same group. In practice, the start-over frequency is extremely small, measured in the range of parts per million for some of our benchmarks.
For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].
06/05/2026
User avatar admin

String added in the repository
reduced hash value is set) and the insertion counter is atomically incremented: if no other thread has incremented the counter during the whole operation (which is checked by comparing with `c0`), then we're good to go and complete the insertion, otherwise we roll back and start over.
This algorithm has very low contention both at the lookup and actual insertion phases in exchange for the possibility that computations have to be started over if some other thread interferes in the process by performing a succesful insertion beginning at the same group. In practice, the start-over frequency is extremely small, measured in the range of parts per million for some of our benchmarks.
06/05/2026
User avatar admin

String added in the repository
When an available slot is located, it is preemptively occupied (its
Lookup is as described above. If lookup finds no equivalent element,
06/05/2026
User avatar admin

String added in the repository
search for an available slot for insertion successively locks/unlocks each group in the probing sequence.
reduced hash value is set) and the insertion counter is atomically incremented: if no other thread has incremented the counter during the whole operation (which is checked by comparing with `c0`), then we're good to go and complete the insertion, otherwise we roll back and start over.
06/05/2026
User avatar admin

String added in the repository
Lookup is as described above. If lookup finds no equivalent element,
The value of the insertion counter for the initial group in the probe
06/05/2026
User avatar admin

String added in the repository
sequence is locally recorded (let's call this value `c0`).
search for an available slot for insertion successively locks/unlocks each group in the probing sequence.
06/05/2026
User avatar admin

String added in the repository
The value of the insertion counter for the initial group in the probe
A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below.
06/05/2026
User avatar admin

String added in the repository
Insertion uses the following _optimistic algorithm_:
sequence is locally recorded (let's call this value `c0`).
06/05/2026

Search