msgid ""
msgstr ""
"Project-Id-Version: Chinese (Simplified Han script) (Boost Unordered "
"Translation (zh_Hans))\n"
"Report-Msgid-Bugs-To: \n"
"POT-Creation-Date: 2026-06-06 23:31+0000\n"
"PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
"Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
"Language-Team: Chinese (Simplified Han script) <https://"
"insights.cppalliance.org/weblate/projects/boost-unordered-documentation-"
"zh_Hans/doc-modules-root-pages-structures-adoc/zh_Hans/>\n"
"Language: zh_Hans\n"
"MIME-Version: 1.0\n"
"Content-Type: text/plain; charset=UTF-8\n"
"Content-Transfer-Encoding: 8bit\n"
"Plural-Forms: nplurals=1; plural=0;\n"
"X-Generator: Weblate 2026.5\n"

#: :1
#, safe-html, strict-same
msgid "[#structures] = Data Structures"
msgstr "[#structures]= 数据结构"

#: :4
#, safe-html, strict-same
msgid ":idprefix: structures_"
msgstr ":idprefix: structures_"

#: :6
#, safe-html, strict-same
msgid "Closed-addressing Containers"
msgstr "闭寻址容器"

#: :16
#, safe-html, strict-same
msgid ""
"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:"
msgstr ""
"Boost.Unordered 提供了速度最快的闭寻址实现之一，该结构通常被称为 https://"
"en.wikipedia.org/wiki/Hash_table#Separate_chaining[分离链接法] 。其数据结构示"
"例如下："

#: :20
#, safe-html, strict-same
msgid "image::bucket-groups.png[align=center]"
msgstr "image::bucket-groups.png[align=center]"

#: :22
#, safe-html, strict-same
msgid ""
"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())`."
msgstr ""
"系统分配一个\"桶\"数组，其中每个桶分别指向其专属的链表。这种结构使得桶迭代能"
"直接满足标准要求。但采用此布局进行整体容器迭代通常较慢，因为需检查每个桶的占"
"用状态，其时间复杂度为 `O(bucket++_++count() {plus} size())` ，而标准要求复杂"
"度应为 `O(size())` 。"

#: :24
#, safe-html, strict-same
msgid ""
"Canonical standard implementations will wind up looking like the diagram "
"below:"
msgstr "典型的标准库实现最终会形成如下图所示的结构："

#: :28
#, safe-html, strict-same
msgid ""
"image::singly-linked.png[align=center,link=_images/singly-"
"linked.png,window=_blank]"
msgstr ""
"image::singly-linked.png[align=center,link=_images/singly-"
"linked.png,window=_blank]"

#: :30
#, safe-html, strict-same
msgid ""
"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]."
msgstr ""
"值得注意的是，这种方法仅被 pass:[libc++] 和 pass:[libstdc++] 所采用；MSVC 的 "
"Dinkumware 实现则使用了不同的方法。关于标准容器的更详细分析可参见 http://"
"bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[此处]。"

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

#: :34
#, safe-html, strict-same
msgid ""
"```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 // ... } ```"
msgstr ""
"```c++ auto const idx = get_bucket_idx(hash_function(key)); node* p = "
"buckets[idx]; // first load node* n = p-&gt;next; // second load if (n "
"&amp;&amp; is_in_bucket(n, idx)) { value_type const&amp; v = *n; // third "
"load // ... } ```"

#: :44
#, safe-html, strict-same
msgid ""
"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 // ... } ```"
msgstr ""
"使用简单的桶组布局，只需执行以下操作：```c++auto const idx = get_bucket_idx"
"(hash_function(key));node* n = buckets[idx]; // 第一次加载if (n) {    "
"value_type const&amp; v = *n; // 第二次加载    // ...}```"

#: :54
#, safe-html, strict-same
msgid ""
"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:"
msgstr ""
"在实际使用中，额外的间接层会对 `insert`、`find` 和 `erase` 等常见操作的性能产"
"生显著影响。但为了保持容器的迭代速度，Boost.Unordered 引入了一种新颖的数据结"
"构——“桶组”。桶组是桶数组的一个固定宽度的子区间视图。它包含一个位掩码（类型为 "
"`std::size_t`），用于跟踪桶的占用情况，并包含两个指针，以便与非空组形成双向链"
"表。下面是一个示例图："

#: :58
#, safe-html, strict-same
msgid "image::fca.png[align=center]"
msgstr "image::fca.png[align=center]"

#: :60
#, safe-html, strict-same
msgid ""
"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."
msgstr ""
"因此，容器范围内的迭代转变为遍历非空的桶组（这是一个具有常数时间复杂度的操作"
"），从而将时间复杂度降回 `O(size())`。总体而言，一个桶组的大小仅为 4 个字，它"
"覆盖 `sizeof(std::size_t) * CHAR_BIT` 个桶，这意味着在所有常见实现中，每个桶"
"由桶组引入的空间开销仅为 4 位。"

#: :62
#, safe-html, strict-same
msgid ""
"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]."
msgstr ""
"关于 Boost.Unordered 闭地址实现的更详细描述，请参阅 https://"
"bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[外部文章]。有关"
"实现原理的更多信息，请阅读 "
"xref:rationale.adoc#rationale_closed_addressing_containers[相应章节]。"

#: :68
#, safe-html, strict-same
msgid "Open-addressing Containers"
msgstr "开放寻址容器"

#: :70
#, safe-html, strict-same
msgid ""
"The diagram shows the basic internal layout of `boost::unordered_flat_set`/"
"`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`."
msgstr ""
"该图展示了 `boost::unordered_flat_set`/`unordered_node_set` 和 "
"`boost::unordered_flat_map`/`unordered_node_map` 的基本内部布局。"

#: :76
#, safe-html, strict-same
msgid "image::foa.png[align=center]"
msgstr "image::foa.png[align=center]"

#: :78
#, safe-html, strict-same
msgid ""
"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."
msgstr ""
"与所有开放寻址容器一样，元素（对于 `boost::unordered++_++node++_++set` 和 "
"`boost::unordered++_++node++_++map`则是元素节点的指针）直接存储在桶数组中。 "
"该数组在逻辑上被划分为 2^_n_^个组，每组包含 15个元素。 除桶数组外，还存在一个"
"关联的__元数据数组__，其中包含 2^_n_^ 个 16 字节的字。"

#: :86
#, safe-html, strict-same
msgid "image::foa-metadata.png[align=center]"
msgstr "image::foa-metadata.png[align=center]"

#: :88
#, safe-html, strict-same
msgid ""
"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:"
msgstr ""
"一个元数据字被划分为 15 个 _h_~_i_~ 字节（每个字节对应一个关联的桶），以及一"
"个 _溢出字节_（图中标记为 _ofw_）。_h_~_i_~ 的值计算方式如下："

#: :91
#, safe-html, strict-same
msgid ""
"- 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."
msgstr ""
"- 0 表示对应的桶为空。\n"
"- 1 用于编码一种特殊的空桶，称为 _哨位桶_，在容器被完全遍历时内部用于停止迭代"
"。\n"
"- 如果桶被占用，则存储从元素哈希值中获得的 _缩减哈希值_。"

#: :97
#, safe-html, strict-same
msgid ""
"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:"
msgstr ""
"当查找一个哈希值为 _h_ 的元素时，可以使用诸如 https://en.wikipedia.org/wiki/"
"SSE2[SSE2] 和 https://en.wikipedia.org/wiki/"
"ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] 等 SIMD 技术，仅需少量 "
"CPU 指令即可快速检查完整的元数据字，并在全部 15 个桶中寻找 _h_ 的缩减值：不匹"
"配的桶可以迅速丢弃，而那些缩减哈希值匹配的桶则需要通过与对应元素的完整比较来"
"进行检查。如果未找到目标元素，则检查溢出字节。"

#: :106
#, safe-html, strict-same
msgid ""
"- 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."
msgstr ""
"- 若位置 _h_ mod 8 的比特位为零，则查找终止（确认元素不存在）。 元素不存在）"
"。 - 若该比特位为1（表示该组已__溢出__），则通过 https://en.wikipedia.org/"
"wiki/Quadratic_probing[_二次探查法_] 检查后续组，并重复此过程。"

#: :112
#, safe-html, strict-same
msgid ""
"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."
msgstr ""
"插入操作的算法逻辑类似：通过 SIMD 技术定位空桶，当遍历到已满的组时，会将其对"
"应的溢出位设置为 1。"

#: :115
#, safe-html, strict-same
msgid ""
"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."
msgstr ""
"在不支持 SIMD 的架构中，逻辑布局保持不变，但元数据字采用一种称为 _位交错_ 的"
"技术进行编码：这种布局允许我们仅使用标准算术和逻辑运算，以相当不错的性能来模"
"拟 SIMD。"

#: :122
#, safe-html, strict-same
msgid "image::foa-metadata-interleaving.png[align=center]"
msgstr "image::foa-metadata-interleaving.png[align=center]"

#: :124
#, safe-html, strict-same
msgid ""
"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]."
msgstr ""
"关于 Boost.Unordered 开放寻址实现的更详细描述，请参阅 https://"
"bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[外部文章]。有"
"关实现原理的更多信息，请阅读 "
"xref:rationale.adoc#rationale_open_addresing_containers[相应章节]。"

#: :130
#, safe-html, strict-same
msgid "Concurrent Containers"
msgstr "并发容器"

#: :132
#, safe-html, strict-same
msgid ""
"`boost::concurrent_flat_set`/`boost::concurrent_node_set` and "
"`boost::concurrent_flat_map`/`boost::concurrent_node_map` use the basic "
"xref:structures.adoc#structures_open_addressing_containers[open-addressing "
"layout] described above augmented with synchronization mechanisms."
msgstr ""
"`boost::concurrent_flat_set`/`boost::concurrent_node_set` 和 "
"`boost::concurrent_flat_map`/`boost::concurrent_node_map` 使用了上述基本的 "
"xref:structures.adoc#structures_open_addressing_containers[开放寻址布局]，并"
"增加了同步机制。"

#: :140
#, safe-html, strict-same
msgid "image::cfoa.png[align=center]"
msgstr "image::cfoa.png[align=center]"

#: :142
#, safe-html, strict-same
msgid "Two levels of synchronization are used:"
msgstr "采用两级同步机制："

#: :144
#, safe-html, strict-same
msgid ""
"Container level: A read-write mutex is used to control access from any "
"operation"
msgstr "容器层面：使用读写互斥锁来控制来自任何操作的访问。"

#: :145
#, safe-html, strict-same
msgid ""
"to the container. Typically, such access is in read mode (that is, "
"concurrent) even for modifying operations, so for most practical purposes "
"there is no thread contention at this level. Access is only in write mode "
"(blocking) when rehashing or performing container-wide operations such as "
"swapping or assignment."
msgstr ""
"对容器的访问。通常情况下，即使是修改操作，此类访问也处于读模式（即并发的），"
"因此在实际使用中，此层面几乎不会发生线程争用。仅在重哈希或执行交换、赋值等容"
"器级操作时，访问才会处于写模式（阻塞）。"

#: :149
#, safe-html, strict-same
msgid ""
"Group level: Each 15-slot group is equipped with an 8-byte word containing:"
msgstr "组级：每个包含15个槽位的组都配备一个8字节的字，其中包含："

#: :150
#, safe-html, strict-same
msgid ""
"** A read-write spinlock for synchronized access to any element in the "
"group. ** An atomic _insertion counter_ used for optimistic insertion as "
"described below."
msgstr ""
"- 一个读写自旋锁，用于同步对组内任何元素的访问。\n"
"- 一个原子 _插入计数器_，用于下文所述的乐观插入。"

#: :154
#, safe-html, strict-same
msgid ""
"By using atomic operations to access the group metadata, lookup is (group-"
"level) lock-free up to the point where an actual comparison needs to be done "
"with an element that has been previously SIMD-matched: only then is the "
"group's spinlock used."
msgstr ""
"通过使用原子操作访问组元数据，查找操作在（组级别）上是无锁的，直到需要与实际"
"进行 SIMD 匹配的元素进行比较时才会使用组的自旋锁。"

#: :158
#, safe-html, strict-same
msgid "Insertion uses the following _optimistic algorithm_:"
msgstr "插入操作使用以下 _乐观算法_："

#: :160
#, safe-html, strict-same
msgid "The value of the insertion counter for the initial group in the probe"
msgstr "探测起始组的插入计数器值"

#: :161
#, safe-html, strict-same
msgid "sequence is locally recorded (let's call this value `c0`)."
msgstr "序列会被本地记录（我们称此值为 `c0`）。"

#: :162
#, safe-html, strict-same
msgid "Lookup is as described above. If lookup finds no equivalent element,"
msgstr "查找过程如上所述。如果查找未找到等效元素，"

#: :163
#, safe-html, strict-same
msgid ""
"search for an available slot for insertion successively locks/unlocks each "
"group in the probing sequence."
msgstr "则会依次对探测序列中的每个组进行加锁/解锁，以搜索可用于插入的空槽位。"

#: :165
#, safe-html, strict-same
msgid "When an available slot is located, it is preemptively occupied (its"
msgstr "当定位到一个可用槽位时，该槽位会被预先占用（其"

#: :166
#, safe-html, strict-same
msgid ""
"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."
msgstr ""
"缩减哈希值被设置），并且插入计数器被原子地递增：如果在整个操作过程中没有其他"
"线程递增该计数器（通过与 `c0` 比较来检查），则插入操作可以顺利完成，否则将回"
"滚并重新开始。"

#: :172
#, safe-html, strict-same
msgid ""
"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."
msgstr ""
"该算法在查找和实际插入阶段都具有非常低的争用，代价是如果其他线程在同一个组上"
"成功执行了插入操作，则当前计算可能需要重新开始。在实际应用中，重新开始的频率"
"极低，根据我们的一些基准测试，其量级在百万分之一以内。"

#: :179
#, safe-html, strict-same
msgid ""
"For more information on implementation rationale, read the "
"xref:rationale.adoc#rationale_concurrent_containers[corresponding section]."
msgstr ""
"如需了解实现原理的更多内容，请参阅 "
"xref:rationale.adoc#rationale_concurrent_containers [对应章节]。"