企业官网建设流程全解析

mold 内置 TBB：concurrent_unordered_multiset 的并行迭代接口（range）与 ContainerRange 实现解析

【免费下载链接】moldmold: A Modern Linker 🦠项目地址: https://gitcode.com/GitHub_Trending/mo/mold

本文以 mold 仓库内置的 TBB 组件中 parallel_iteration.rst 规范文档为主体，系统讲解concurrent_unordered_multiset容器用于并行算法遍历的range_type/const_range_type成员类型与range()成员函数的语义、约束与契约，并结合 TBB 源码中的实现与测试用例说明其拆分（splitting）机制，帮助读者掌握"如何把并发容器安全地喂给parallel_for等并行原语"这一实战方案。

一、为什么并发容器需要专门的并行迭代接口

concurrent_unordered_multiset是一个允许多线程并发插入、查找的哈希容器（"multiset" 即允许重复键）。它不能像std::unordered_set那样简单地"边遍历边处理"：遍历期间其他线程可能正在插入或删除节点。TBB 的解决方案是提供一类满足ContainerRange要求的 range 对象——它本质上是一段可递归二分的工作区间，而不是传统意义上的迭代器区间。这样parallel_for、parallel_reduce等算法可以不断地调用"拆分构造器"把区间切成两半，直到每一块小到适合串行执行，从而在不加全局锁的情况下实现安全的并行遍历。

这一点在规范中直接写明：ContainerRange对象"可以用于parallel_for等并行算法中遍历容器"（参见 ContainerRange 需求文档）。

二、成员类型：range_type 与 const_range_type

原文档的核心内容是对两个成员类型的界定：

成员类型concurrent_unordered_multiset::range_type和concurrent_unordered_multiset::const_range_type满足ContainerRange要求；这两种类型唯一的区别在于：const_range_type的边界（bounds）类型是concurrent_unordered_multiset::const_iterator，而range_type的边界类型是concurrent_unordered_multiset::iterator。

即二者功能完全一致，只是返回的可变/只读迭代器不同。容器侧的配套迭代器接口定义在同章节的 iterators.rst：iterator与const_iterator满足 ISO C++ 标准[forward.iterators]的 ForwardIterator 要求，并提供begin()/cbegin()（指向第一个元素）与end()/cend()（指向尾后位置）。

三、range() 成员函数

原文档给出的接口签名与语义：

range_type range(); // 非 const 容器上调用 const_range_type range() const; // const 容器上调用

Returns：返回一个表示"容器内全部元素"的 range 对象。

也就是说，拿到容器的完整并行迭代入口只需要一行：对非 const 容器调用range()得到range_type，对 const 容器得到const_range_type。返回的 range 对象覆盖容器当前时刻的全部元素，可被反复拆分。

四、ContainerRange 契约：range 对象必须满足哪些要求

ContainerRange 需求文档（需求编号req.container_range）规定了满足该契约的类型必须同时满足两部分要求。

4.1 必须满足 Range 要求

首先它要满足 Range 要求（req.range）：一个 range 可以被递归二分为两部分，拆分通过调用其"拆分构造器"完成。Range 要求包括：

R::R( const R& ); // 拷贝构造 bool empty() const; // 区间是否为空 bool is_divisible() const; // 是否可以再拆分为两个子区间 R::R( R& r, split ); // 基本拆分构造器：把 r 拆成两个子区间 R::R( R& r, proportional_split ); // 可选：按给定比例拆分

规范还约定了拆分的方向性：若值集合存在"方向"，拆分构造器应构造区间的后半部分并更新入参为前半部分，这样parallel_for/parallel_reduce/parallel_scan在退化为串行执行时会按递增顺序处理区间，与普通顺序循环的行为一致。

4.2 必须提供的成员类型与函数

在此之上，ContainerRange还要求提供：

对concurrent_unordered_multiset的两种 range 类型而言，这些成员在iterator一项上体现为上文提到的唯一差异：range_type::iterator是iterator，const_range_type::iterator是const_iterator。

五、源码实现解析：range 对象如何被拆分

规范只描述契约，真正的实现在 TBB 容器基类头文件 中（concurrent_unordered_set与concurrent_unordered_multiset都继承自concurrent_unordered_base，后者携带allow_multimapping = true的特征参数，见 concurrent_unordered_set.h）。

5.1 const_range_type：持有区间边界与中点

源码中const_range_type的核心成员变量是四个节点指针：

const concurrent_unordered_base& my_instance; // 所属容器 node_ptr my_begin_node; // 区间起点 node_ptr my_end_node; // 区间终点（尾后） mutable node_ptr my_midpoint_node; // 预计算的中点，用于下次拆分

它对外提供的接口与契约一一对应：

• empty()：my_begin_node == my_end_node时为空；
• is_divisible()：my_midpoint_node != my_end_node时仍可以再拆分；
• grainsize()：直接返回1，即最小工作单元是单个元素；
• begin()/end()：从边界节点取出第一个"值节点"（first_value_node）包装成迭代器返回。

5.2 拆分构造器：O(1) 对半分

拆分构造器的语义是：新对象"拿走"原区间的后半段（原中点 → 原终点），原对象收缩为前半段（原点 → 原中点），然后双方各自重新计算自己的中点：

const_range_type( const_range_type& range, split ) : my_instance(range.my_instance), my_begin_node(range.my_midpoint_node), // 新对象从原中点开始 my_end_node(range.my_end_node) // 到原终点结束 { range.my_end_node = my_begin_node; // 原对象收缩到原中点 ... set_midpoint(); range.set_midpoint(); }

由于中点在区间创建/上一次拆分时已预先计算好，每次拆分本身是 O(1) 的指针操作。

5.3 中点如何找到：借助段表与 reverse_bits

concurrent_unordered_base内部采用哈希段表（segment table）组织节点。set_midpoint()的思路是：

1. 取my_begin_node与my_end_node的order_key()（节点在段表中的有序键），计算二者的中点键值；
2. 对mid_bucket键执行reverse_bits（按位反转）后对当前桶数取模，定位一个候选段表桶；若该桶为空则通过get_parent(mid_bucket)向上回溯到最近非空祖先；
3. 若反转后的桶号确实落在 begin 与 end 的 order_key 之间，说明区间内部存在一个"dummy 节点"（段表占位节点），于是取该段第一个值节点作为中点；否则区间内没有可切分点，中点退化为my_end_node，表示该区间不可再拆。

可以推断，这一设计利用了哈希容器的段表结构：dummy 节点把整个键空间划分成连续段，按中点键在段表中定位就能以接近 O(1) 的成本获得"大约一半"的切分位置，而不必真的数出元素个数——这正是并发容器（无法随时安全地全量遍历计数）能做到高效递归拆分的根本原因。

5.4 range_type：继承并只改迭代器类型

range_type 的完整定义只有 8 行，它继承const_range_type，复用拷贝构造与拆分构造器（using const_range_type::const_range_type;），仅重写begin()/end()把底层的const_iterator适配成iterator。这与规范"两种类型仅边界迭代器类型不同"的描述完全一致。容器侧的range()两个重载分别返回range_type(*this)与const_range_type(*this)（源码）。

六、实战用法与测试验证

6.1 与 parallel_for 配合遍历

range 对象的标准用法是作为parallel_for的第一个参数，lambda 捕获容器（或 range）后按迭代器遍历子区间：

#include "oneapi/tbb/concurrent_unordered_set.h" #include "oneapi/tbb/parallel_for.h" tbb::concurrent_unordered_multiset<int> table; // ... 多线程并发插入若干元素 ... // 并行遍历：range 可被算法不断拆分为更小的子区间 tbb::parallel_for( table.range(), []( tbb::concurrent_unordered_multiset<int>::range_type r ) { for (auto it = r.begin(); it != r.end(); ++it) { // 处理元素 *it（此处可只读访问元素） } } );

测试代码中即有完全相同形态的用例：concurrent_associative_common.h 同时对可变容器c与 const 容器constC的range()执行tbb::parallel_for，分别验证可变与只读两条路径。

6.2 测试用例对契约的逐条验证

TBB 的公共测试头 concurrent_associative_common.h 对 range 契约做了系统断言：

• 空容器的 range 行为（L428-L436）：空容器上range()得到的区间必须empty()、!is_divisible()，且r.begin() == r.end()、r.begin() == cont.begin()；
• 递归拆分完整性（L644-L649）：向容器插入 256 个元素后，CheckRecursiveRange对range()递归二分直至不可拆，累加各叶子区间的元素数应恰好等于 256（可变迭代器与 const 迭代器两条路径分别验证）；同时断言grainsize() > 0。

这组断言恰好覆盖第四节列出的契约要点：空语义、可分性、迭代器边界、grainsize 与递归拆分的完备性（不重不漏）。

七、要点回顾

1. concurrent_unordered_multiset提供range_type range()与const_range_type range() const两个重载，返回表示"容器全部元素"的可递归拆分区间，二者唯一区别是边界迭代器类型（iteratorvsconst_iterator）；
2. range 对象满足ContainerRange契约：在Range要求（empty/is_divisible/split拆分构造器）之上，额外提供value_type、reference、iterator、size_type、begin()/end()/grainsize()等成员；
3. 实现上，中点借助哈希段表与reverse_bits中点键定位，使每次拆分接近 O(1)，且区间不可再拆时is_divisible()返回 false，保证算法可安全终止；
4. 实战中把cont.range()直接传给tbb::parallel_for（或其 const 版本）即可完成并发遍历，仓库测试已按契约对空容器、递归拆分完整性等场景做了覆盖，可作为编写自定义 range 时的参照。

【免费下载链接】moldmold: A Modern Linker 🦠项目地址: https://gitcode.com/GitHub_Trending/mo/mold