msgid "" msgstr "" "Project-Id-Version: English (Boost Unordered Translation (zh_Hans))\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2026-06-06 21:29+0000\n" "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n" "Last-Translator: FULL NAME \n" "Language-Team: English \n" "Language: en\n" "MIME-Version: 1.0\n" "Content-Type: text/plain; charset=UTF-8\n" "Content-Transfer-Encoding: 8bit\n" "Plural-Forms: nplurals=2; plural=n != 1;\n" "X-Generator: Weblate 2026.5\n" #: :1 #, read-only, safe-html, strict-same msgid "[#structures] = Data Structures" msgstr "[#structures] = Data Structures" #: :4 #, read-only, safe-html, strict-same msgid ":idprefix: structures_" msgstr ":idprefix: structures_" #: :6 #, read-only, safe-html, strict-same msgid "Closed-addressing Containers" msgstr "Closed-addressing Containers" #: :16 #, read-only, 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 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:" #: :20 #, read-only, safe-html, strict-same msgid "image::bucket-groups.png[align=center]" msgstr "image::bucket-groups.png[align=center]" #: :22 #, read-only, 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 "" "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())`." #: :24 #, read-only, safe-html, strict-same msgid "" "Canonical standard implementations will wind up looking like the diagram " "below:" msgstr "" "Canonical standard implementations will wind up looking like the diagram " "below:" #: :28 #, read-only, 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 #, read-only, 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 "" "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]." #: :32 #, read-only, 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 "" "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:" #: :34 #, read-only, 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->next; // second load if (n && " "is_in_bucket(n, idx)) { value_type const& v = *n; // third load // ... } ```" #: :44 #, read-only, 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 "" "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 // ... } ```" #: :54 #, read-only, 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 "" "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:" #: :58 #, read-only, safe-html, strict-same msgid "image::fca.png[align=center]" msgstr "image::fca.png[align=center]" #: :60 #, read-only, 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 "" "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." #: :62 #, read-only, 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 "" "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]." #: :68 #, read-only, safe-html, strict-same msgid "Open-addressing Containers" msgstr "Open-addressing Containers" #: :70 #, read-only, 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 "" "The diagram shows the basic internal layout of `boost::unordered_flat_set`/" "`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`." #: :76 #, read-only, safe-html, strict-same msgid "image::foa.png[align=center]" msgstr "image::foa.png[align=center]" #: :78 #, read-only, 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 "" "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." #: :86 #, read-only, safe-html, strict-same msgid "image::foa-metadata.png[align=center]" msgstr "image::foa-metadata.png[align=center]" #: :88 #, read-only, 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 "" "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:" #: :91 #, read-only, 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 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." #: :97 #, read-only, 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 "" "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:" #: :106 #, read-only, 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 "" "- 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." #: :112 #, read-only, 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 "" "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." #: :115 #, read-only, 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 "" "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." #: :122 #, read-only, safe-html, strict-same msgid "image::foa-metadata-interleaving.png[align=center]" msgstr "image::foa-metadata-interleaving.png[align=center]" #: :124 #, read-only, 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 "" "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]." #: :130 #, read-only, safe-html, strict-same msgid "Concurrent Containers" msgstr "Concurrent Containers" #: :132 #, read-only, 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` 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." #: :140 #, read-only, safe-html, strict-same msgid "image::cfoa.png[align=center]" msgstr "image::cfoa.png[align=center]" #: :142 #, read-only, safe-html, strict-same msgid "Two levels of synchronization are used:" msgstr "Two levels of synchronization are used:" #: :144 #, read-only, safe-html, strict-same msgid "" "Container level: A read-write mutex is used to control access from any " "operation" msgstr "" "Container level: A read-write mutex is used to control access from any " "operation" #: :145 #, read-only, 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 "" "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." #: :149 #, read-only, safe-html, strict-same msgid "" "Group level: Each 15-slot group is equipped with an 8-byte word containing:" msgstr "" "Group level: Each 15-slot group is equipped with an 8-byte word containing:" #: :150 #, read-only, 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 "" "** A read-write spinlock for synchronized access to any element in the " "group. ** An atomic _insertion counter_ used for optimistic insertion as " "described below." #: :154 #, read-only, 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 "" "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." #: :158 #, read-only, safe-html, strict-same msgid "Insertion uses the following _optimistic algorithm_:" msgstr "Insertion uses the following _optimistic algorithm_:" #: :160 #, read-only, safe-html, strict-same msgid "The value of the insertion counter for the initial group in the probe" msgstr "The value of the insertion counter for the initial group in the probe" #: :161 #, read-only, safe-html, strict-same msgid "sequence is locally recorded (let's call this value `c0`)." msgstr "sequence is locally recorded (let's call this value `c0`)." #: :162 #, read-only, safe-html, strict-same msgid "Lookup is as described above. If lookup finds no equivalent element," msgstr "Lookup is as described above. If lookup finds no equivalent element," #: :163 #, read-only, safe-html, strict-same msgid "" "search for an available slot for insertion successively locks/unlocks each " "group in the probing sequence." msgstr "" "search for an available slot for insertion successively locks/unlocks each " "group in the probing sequence." #: :165 #, read-only, safe-html, strict-same msgid "When an available slot is located, it is preemptively occupied (its" msgstr "When an available slot is located, it is preemptively occupied (its" #: :166 #, read-only, 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 "" "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." #: :172 #, read-only, 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 "" "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." #: :179 #, read-only, safe-html, strict-same msgid "" "For more information on implementation rationale, read the " "xref:rationale.adoc#rationale_concurrent_containers[corresponding section]." msgstr "" "For more information on implementation rationale, read the " "xref:rationale.adoc#rationale_concurrent_containers[corresponding section]."