企业官网建设流程全解析

oneapi::tbb::concurrent_multimap 并行迭代（Parallel Iteration）机制详解：range_type 与 range() 的源码级剖析

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

oneapi::tbb::concurrent_multimap是 oneTBB（oneAPI Threading Building Blocks）提供的、基于并发跳表实现的排序关联容器，支持多线程并发插入、查找与遍历，并允许同一键对应多个值。要在多线程环境中高效地"并行遍历"整个容器，官方规范通过成员类型range_type/const_range_type与成员函数range()给出了标准入口：它们把容器整体建模为一个满足 ContainerRange 要求的 range 对象，可直接交给parallel_for等并行算法进行分治式处理。本文以 parallel_iteration.rst 规范文档为主线，结合容器类模板声明、ContainerRange 命名要求以及底层concurrent_skip_list实现，完整讲清 range 类型的设计、range()的语义与典型并行用法，读完即可在自己的并发程序里安全地写出并行遍历concurrent_multimap的代码。

一、规范文档说了什么：并行迭代的契约

parallel_iteration.rst 是 concurrent_multimap 类规范 中 "Parallel iteration" 一节的正文，其核心内容可归纳为三点契约：

1. 类型满足命名要求：concurrent_multimap::range_type与concurrent_multimap::const_range_type均满足 ContainerRange requirements（在类规范中标注为 [req.container_range]）。
2. 两者的唯一差异在迭代器类型：const_range_type的边界（bounds）是concurrent_multimap::const_iterator，而range_type的边界是concurrent_multimap::iterator。也就是说，两个 range 类型的行为完全一致，只是可变与只读的区别。
3. range 成员函数的返回语义：无参调用range()返回一个表示"容器中全部元素"的 range 对象；const 重载返回const_range_type，非 const 重载返回range_type。

对应到 concurrent_multimap 类模板摘要 中的声明：

// Parallel iteration range_type range(); const_range_type range() const;

从声明可以看出：对非常量对象调用range()得到一个"可读写元素"的 range；对常量对象（或通过 const 引用访问）调用则得到只读 range。两者可以安全地用于parallel_for等并行算法。

二、ContainerRange 命名要求：range 对象必须提供什么

要理解range_type的能力，必须先看懂 container_range.rst 定义的 ContainerRange 命名要求。该文档指出：

ContainerRangeis a range that represents a concurrent container or a part of the container. TheContainerRangeobject can be used to traverse the container in parallel algorithms likeparallel_for.

一个类型CR满足 ContainerRange 要求需要同时满足：

• Range 要求：CR满足 Range requirements（oneTBB 并行算法的 range 基本要求，即支持begin()/end()与grainsize()，并支持通过split构造进行区间切分）；
• 提供如下成员类型与函数：

正是这套统一接口，使得 range 对象可以无缝接入parallel_for/parallel_reduce等算法——算法通过反复调用split构造函数把 range 一分为二，直到子 range 的大小不超过grainsize()，从而把遍历工作均衡地分发到多个线程。

三、源码实现：range 类型长什么样

规范中的"implementation-defined range"在 oneTBB 当前仓库中的真实实现位于 detail/_concurrent_skip_list.h。concurrent_multimap与concurrent_map都继承自concurrent_skip_list（见 oneapi/tbb/concurrent_map.h），因此 range 能力统一由跳表基类提供。

3.1 只读 range：const_range_type

class const_range_type { public: using size_type = typename concurrent_skip_list::size_type; using difference_type = typename concurrent_skip_list::difference_type; using iterator = typename concurrent_skip_list::const_iterator; using value_type = typename iterator::value_type; size_type size() const { return std::distance(my_begin, my_end); } const_range_type( const_range_type& r, split) : my_end(r.my_end) { if (r.empty()) { __TBB_ASSERT(my_end.my_node_ptr == nullptr, nullptr); my_begin = my_end; my_level = 0; // ... } else { my_level = my_begin.my_node_ptr->height(); } r.my_end = my_begin; } const_range_type( const concurrent_skip_list& l) : my_end(l.end()), my_begin(l.begin()), my_level(my_begin.my_node_ptr ? my_begin.my_node_ptr->height() : 0) {} iterator begin() const { return my_begin; } iterator end() const { return my_end; } // ... private: const_iterator my_end; const_iterator my_begin; size_type my_level; }; // class const_range_type

实现要点：

• 数据成员只有my_begin、my_end两个const_iterator，以及一个用于辅助分片的my_level（记录切分点节点的跳表高度，供split构造时在中间位置断开区间）。
• split构造函数是 range 能被并行分治的核心：它以"切走前半段"的方式工作——新对象接管r的my_end，而r的my_end被更新为新对象的my_begin，从而把原 range 切成前后两段；my_level取切分点节点的高度，用于控制后续切分的平衡性。
• begin()/end()直接透传底层 const 迭代器，满足 ContainerRange 的迭代接口。
• 与规范一致，const_range_type的边界类型就是const_iterator。

3.2 可变 range：range_type 继承 const_range_type

class range_type : public const_range_type { public: using iterator = typename concurrent_skip_list::iterator; using value_type = typename iterator::value_type; using reference = typename iterator::reference; // ... iterator end() const { node_ptr node = const_range_type::end().my_node_ptr; return iterator(node); } }; // class range_type

range_type公有继承const_range_type，仅在接口层面把迭代器类型替换为可变的iterator（end()从基类的 const 迭代器包装出可变迭代器）。这正好印证了规范文档的那句话：两种 range 类型只差在边界迭代器的可变性上，其余行为完全一致。

3.3 range() 成员函数的真实定义

range_type range() { return range_type(*this); } const_range_type range() const { return const_range_type(*this); }

• 非 const 版本用*this构造range_type：range 的边界是可变迭代器，允许在遍历过程中修改元素；
• const 版本用*this构造const_range_type：边界是 const 迭代器，只能读取元素。

两个版本返回的 range 都覆盖容器"全部元素"（构造时以begin()/end()为界），与规范文档 "Returns: a range object representing all elements in the container" 的语义完全一致。

从容器实现看，concurrent_multimap通过concurrent_skip_list<map_traits<Key, Value, Compare, geometric_level_generator<32>, Allocator, true>>实例化而来（oneapi/tbb/concurrent_map.h），AllowMultimapping = true正是"允许多个相同键共存"的开关，即 multimap 语义；其底层使用geometric_level_generator<32>生成跳表节点层数（最多 32 层），支撑并发的插入、查找与遍历。因此 range 遍历的底层数据结构是并发跳表，而不是红黑树——这一点与标准库std::multimap有本质区别，也是它支持无锁并发读与并发写的前提。

四、实战：用 range() 驱动 parallel_for 并行遍历

ContainerRange 设计的目的就是与parallel_for这类并行算法协作。下面是一个可直接落地的完整示例：多个线程并发地向concurrent_multimap插入数据，然后通过range()把整个容器并行遍历一遍，累计统计键值总和。

#include <oneapi/tbb/concurrent_map.h> #include <oneapi/tbb/parallel_for.h> #include <cstdio> int main() { oneapi::tbb::concurrent_multimap<int, int> mm; // 阶段一：多线程并发插入（同一键可多次插入，multimap 语义） oneapi::tbb::parallel_for(0, 10000, & { mm.emplace(i % 100, i); // 键 0..99，每个键对应约 100 个值 }); // 阶段二：通过 range() 并行遍历容器全部元素 long long sum = 0; oneapi::tbb::parallel_for(mm.range(), & { long long local = 0; for (auto it = r.begin(); it != r.end(); ++it) local += it->second; __atomic_fetch_add(&sum, local, __ATOMIC_RELAXED); }); std::printf("total elements: %zu\n", mm.size()); std::printf("sum: %lld\n", sum); return 0; }

关键点说明：

• mm.range()返回range_type，被parallel_for作为 range 参数接收；parallel_for会自动调用split构造函数把 range 切分为多个子区间，分发到不同线程并行执行。
• 在 lambda 内部通过r.begin()/r.end()遍历子区间；因为 range 的边界是普通iterator，遍历时也可以就地修改it->second（前提是保证不同线程不修改同一元素，或借助原子操作）。
• 求和这类"各线程独立累计再合并"的模式，更地道的做法是直接使用parallel_reduce+range()；上面用原子累加只是展示 range 的遍历形态。
• 若只想读取而不修改，可以写const auto& cm = mm; cm.range();来获得const_range_type。

五、为什么 range() 比 begin()/end() 更适合并行

很多初次接触的用户会问：直接用mm.begin()/mm.end()不也能遍历吗？两者关键区别在于可切分性（splittable）：

• begin()/end()返回的迭代器对只是一条线性区间，无法在不持有容器内部结构信息的情况下均衡切分；
• range_type是满足 Range 要求的对象，内置split构造与grainsize()接口，parallel_for可以反复二分直到子区间足够小，实现负载均衡；
• 迭代器版本只能单线程线性遍历，无法发挥多核并行能力。

此外，concurrent_multimap支持并发插入、查找和遍历，但不支持并发删除（规范中删除接口以unsafe_erase/unsafe_extract命名，见 concurrent_multimap_cls.rst）。因此在使用range()并行遍历时，允许其他线程同时执行插入或查找，但不要并发调用任何unsafe_*修改接口，否则会破坏遍历的一致性。

六、总结

• 规范层面：concurrent_multimap::range_type/const_range_type满足 ContainerRange 命名要求，二者仅边界迭代器可变性不同；range()返回覆盖全部元素的 range 对象（parallel_iteration.rst）。
• 实现层面：range 类型由并发跳表基类 detail/_concurrent_skip_list.h 提供，const_range_type持有 begin/end 两个 const 迭代器并提供split构造，range_type继承之并将迭代器升级为可变；range()两个重载分别返回两种 range。
• 用法层面：mm.range()可直接作为parallel_for/parallel_reduce的 range 参数，实现多线程并行遍历；遍历期间可并发插入与查找，但需避免并发删除。

掌握range()与 range 类型，就能把concurrent_multimap的并发插入能力与 oneTBB 并行算法的分治遍历能力组合起来，写出既安全又充分利用多核的并发容器处理代码。

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