并发编程高性能计算【免费下载链接】oneTBBoneAPI Threading Building Blocks (oneTBB)项目地址https://gitcode.com/gh_mirrors/on/oneTBB点击查看免费下载摘要导读oneapi::tbb::concurrent_multimap是 oneAPI Threading Building BlocksoneTBB提供的支持并发插入、查找与遍历的有序关联容器与std::multimap类似它允许容器中存储多个键相等的元素。本文聚焦该容器以及其孪生容器concurrent_map的迭代器接口完整解析begin()/cbegin()/end()/cend()的语义、ForwardIterator 标准要求、底层跳表skip list实现原理以及多线程场景下迭代遍历必须注意的安全边界问题。读完本文你将能正确、安全地在并发环境中使用 oneTBB 的 multimap 迭代器完成遍历、查找与并行迭代并理解其行为与 STL 容器的差异。一、迭代器类型的标准要求在 concurrent_multimap 类模板概要 中concurrent_multimap定义了如下两个迭代器类型成员类型说明iterator实现定义的ForwardIterator前向迭代器const_iterator实现定义的常量前向迭代器对value_type只读根据 迭代器参考文档concurrent_multimap::iterator与concurrent_multimap::const_iterator都满足 ISO C 标准 [forward.iterators] 一节对ForwardIterator的要求。这意味着它们支持单向遍历it与it可以沿容器方向前进但不支持--it倒退支持*it解引用与it-member访问仅当迭代器非 end 时支持相等/不等比较/!支持默认构造、拷贝构造与赋值同一容器的迭代器可多次遍历且可同时使用多个迭代器多遍保证。由于它只是ForwardIterator而非随机访问迭代器不能对它执行it n、it - n、it[n]或it1 it2等随机访问运算这与std::multimap的迭代器行为一致。从源码确认类型定义在 include/oneapi/tbb/concurrent_map.h 中concurrent_multimap的迭代器类型定义如下// include/oneapi/tbb/concurrent_map.h class concurrent_multimap : public concurrent_skip_listmap_traitsKey, Value, Compare, geometric_level_generator32, Allocator, true { ... using iterator typename base_type::iterator; using const_iterator typename base_type::const_iterator; ... };注意模板参数AllowMultimapping true最后一个布尔参数这正是 multimap 与 map 在底层实现上的关键区别concurrent_map对应false键唯一concurrent_multimap对应true允许键重复。两种容器共用同一套跳表实现concurrent_skip_list因此迭代器类型与遍历语义完全一致。在底层 include/oneapi/tbb/detail/_concurrent_skip_list.h 中具体迭代器类型为using iterator skip_list_iteratorlist_node_type, value_type; using const_iterator skip_list_iteratorlist_node_type, const value_type;即iterator与const_iterator是同一个模板skip_list_iteratorNodeType, ValueType的两个实例化差别仅在于第二个模板参数是否带constconst_iterator解引用得到的是const value_type。value_type为std::pairconst key_type, mapped_type见map_traits定义include/oneapi/tbb/concurrent_map.h与std::multimap一致——键是 const 的不能通过迭代器修改键。二、begin 与 cbegin定位首个元素iterators.rst 给出了三个获取容器起始迭代器的成员函数iterator begin(); const_iterator begin() const; const_iterator cbegin() const;返回指向容器中第一个元素的迭代器。非 const 对象调用begin()得到iterator可读写元素可修改 mapped 值不可修改键const 对象调用begin()得到const_iterator只读cbegin()无论对象是否为 const 都返回const_iterator用于明确表达只读遍历意图。这里第一个元素按键的升序确定concurrent_multimap是有序容器其顺序由模板参数Compare默认std::lessKey决定。若容器为空begin()返回的迭代器与end()相等。从源码结构看跳表的最底层level 0是一条完整的有序链表begin()即指向这条链表的头节点之后的首个元素节点skip_list_iterator::operator通过my_node_ptr-next(0)沿 level 0 前进include/oneapi/tbb/detail/_concurrent_skip_list.h从而保证迭代按升序遍历全部元素。使用示例#include oneapi/tbb/concurrent_map.h #include iostream using oneapi::tbb::concurrent_multimap; int main() { concurrent_multimapint, std::string mm; mm.emplace(2, two-a); mm.emplace(1, one); mm.emplace(2, two-b); // 与 2 键重复multimap 允许 // 非 const 遍历begin() 返回 iterator for (auto it mm.begin(); it ! mm.end(); it) { std::cout it-first - it-second \n; } // 只读遍历cbegin() 永远返回 const_iterator const auto cmm mm; for (auto cit cmm.cbegin(); cit ! cmm.cend(); cit) { // cit-second x; // 错误const_iterator 不允许修改 } return 0; }输出将按键升序排列键1在键2之前两个键为2的元素会相邻出现。三、end 与 cend定位尾部哨兵同样由 iterators.rst 给出iterator end(); const_iterator end() const; const_iterator cend() const;返回指向最后一个元素之后位置past-the-end的迭代器。end()/cend()返回的是哨兵迭代器它不指向任何真实元素不能被解引用*end()或end()-...都是未定义行为。它主要用于作为遍历循环的终止条件it ! end()与begin()配对构成[begin(), end())半开区间这是所有标准容器遍历的惯用写法作为查找/插入失败时的返回标记例如find未命中时返回end()参考 查找操作。判断容器是否为空可以写作begin() end()或cbegin() cend()oneTBB 的并发容器测试在构造后也以此方式校验迭代器状态见 test/common/concurrent_associative_common.hREQUIRE_MESSAGE(cont.cbegin() cont.cend(), Concurrent container iterators are invalid after construction)。四、迭代器底层实现剖析跳表与 skip_list_iterator要正确理解这些迭代器在多线程下的行为有必要看一下底层的实现机制。concurrent_multimap与concurrent_map都构建在**并发跳表concurrent skip list**之上// include/oneapi/tbb/detail/_concurrent_skip_list.h template typename NodeType, typename ValueType class skip_list_iterator { public: using iterator_category std::forward_iterator_tag; using value_type ValueType; using difference_type std::ptrdiff_t; using pointer value_type*; using reference value_type; skip_list_iterator() : skip_list_iterator(nullptr) {} ... reference operator*() const { return my_node_ptr-value(); } pointer operator-() const { return my_node_ptr-storage(); } skip_list_iterator operator() { __TBB_ASSERT(my_node_ptr ! nullptr, nullptr); my_node_ptr my_node_ptr-next(0); return *this; } ... private: node_ptr my_node_ptr; };几个值得注意的实现细节iterator_category被显式声明为std::forward_iterator_tag与文档声称的ForwardIterator要求完全一致operator沿 level 0最底层前进跳表节点持有一个原子指针数组atomic_node_ptrinclude/oneapi/tbb/detail/_concurrent_skip_list.hnext(0)返回第 0 层的后继节点指针。高层指针用于加速查找跳跃前进而迭代遍历始终走完整有序的底层链表因此迭代顺序即键的升序operator内部带断言当迭代器为 null默认构造或已到达 end时继续会在调试版本触发__TBB_ASSERT提示这是非法操作const_iterator是同一模板以const value_type实例化的结果所以const_iterator的operator*返回const value_type迭代器内部保存的是节点指针my_node_ptr而非节点的副本——这正是理解并发语义的关键。五、并发遍历的安全边界何时可以用 begin/end 遍历这是使用concurrent_multimap迭代器时最需要厘清的问题也是它和std::multimap最大的行为差异。1. 迭代器本身不是线程安全的iterator/const_iterator对象不提供并发保护。同一迭代器对象不能被多个线程同时使用例如一个线程在it的同时另一个线程读取*it。正确的做法是每个线程持有自己的迭代器。2. 遍历与并发插入、查找可安全共存concurrent_multimap支持并发的插入、查找与遍历参考 concurrent_multimap 概述。也就是说其他线程正在emplace/insert/find/count时本线程可以安全地用begin()到end()遍历容器遍历过程中插入的新元素不保证被当前遍历看到可能看到也可能看不到遍历过程中不会因为其他线程的插入而崩溃或读到损坏数据——跳表节点的原子指针与内存顺序保证了结构一致性。3. 遍历与并发删除不能共存concurrent_multimap不支持并发的 erase它只提供unsafe_erase等不安全删除接口。如果在一个线程遍历的同时另一个线程执行删除行为是未定义的。这是文档明确标注的边界安全修改操作 中不含 erase删除类操作全部归入 不安全修改操作unsafe_erase、unsafe_extract等并要求调用者保证此时没有其他线程正在访问容器。结论在 oneTBB 的 multimap 上begin()/end()遍历只保证与并发插入 并发查找共存不与并发删除共存。这正是跳表结构换来的便利与代价。六、从迭代器到并行迭代range() 的进阶用法迭代器不仅是串行遍历的入口也是并行算法的桥梁。concurrent_multimap提供了range()成员函数返回一个可被 oneTBB 并行算法消费的容器区间对象参考 并行迭代文档range_type range(); const_range_type range() const;range_type与const_range_type满足 oneTBB 的ContainerRange命名需求两者唯一区别是区间边界迭代器的类型range_type的边界是iteratorconst_range_type的边界是const_iterator返回的 range 对象表示容器中的全部元素。典型用法是与parallel_for结合对 multimap 的全部元素做并行处理#include oneapi/tbb/concurrent_map.h #include oneapi/tbb/parallel_for.h #include oneapi/tbb/blocked_range.h using oneapi::tbb::concurrent_multimap; void process_all(concurrent_multimapint, int mm) { oneapi::tbb::parallel_for(mm.range(), { for (auto it r.begin(); it ! r.end(); it) { // 并行处理 [r.begin(), r.end()) 内的元素 } }); }注意与迭代器遍历的约束一致range()的并行迭代同样要求没有并发的删除操作否则行为未定义。此外oneTBB 还支持通过parallel_for_each等算法直接配合这些容器使用相关公共测试基础设施见 test/common/concurrent_associative_common.h。七、最佳实践速查场景推荐写法说明读写遍历非 const 容器for (auto it mm.begin(); it ! mm.end(); it)可修改 mapped 值只读遍历for (auto it mm.cbegin(); it ! mm.cend(); it)语义明确const 友好判断空容器mm.begin() mm.end()等价于empty()遍历同时他人插入/查找安全oneTBB 保证结构一致性遍历同时他人删除禁止未定义行为请使用unsafe_erase前先停止并发访问共享同一迭代器对象跨线程禁止每线程各自持有迭代器对end()解引用或越过 end禁止未定义行为调试版会触发__TBB_ASSERT核心要点回顾concurrent_multimap::iterator与const_iterator满足 C 标准的ForwardIterator要求只能单向递增遍历begin()/cbegin()返回指向最小键元素的迭代器end()/cend()返回尾后哨兵底层是并发跳表迭代沿 level 0 有序链表前进因此遍历顺序按键升序遍历安全地与并发插入、查找共存但绝不能在并发删除时遍历需要并行处理全部元素时优先用range()配合parallel_for比手写多线程切分更安全高效。参考与延伸阅读本文主文档concurrent_multimap 迭代器参考concurrent_multimap 类模板概要完整成员类型与接口总览查找操作find、count、equal_range与迭代器的协作并行迭代range()与并行算法安全/不安全修改操作 与 不安全修改操作明确 erase 的并发边界实现源码include/oneapi/tbb/concurrent_map.h、include/oneapi/tbb/detail/_concurrent_skip_list.h测试参考test/common/concurrent_associative_common.h迭代器构造/遍历相关断言、test/tbb/test_concurrent_map.cpp容器行为测试赞分享并发编程高性能计算【免费下载链接】oneTBBoneAPI Threading Building Blocks (oneTBB)项目地址https://gitcode.com/gh_mirrors/on/oneTBB点击查看免费下载相关推荐oneTBB concurrent_unordered_multimap 迭代器完全指南begin/cbegin/end/cend 与 ForwardIterator 语义解析oneTBB concurrent_unordered_multimap 迭代器完全指南begin/cbegin/end/cend 与 ForwardIter并发编程高性能计算oneTBB concurrent_unordered_multiset 迭代器完全指南begin/end 接口、ForwardIterator 语义与源码级实现剖析oneTBB concurrent_unordered_multiset 迭代器完全指南begin/end 接口、ForwardIterator 语义与源码级并发编程高性能计算oneTBB 并发多重集合 concurrent_multiset 迭代器完全指南begin/cbegin/end/cend 与 ForwardIterator 语义解析oneTBB 并发多重集合 concurrent_multiset 迭代器完全指南begin/cbegin/end/cend 与 ForwardIterato并发编程高性能计算创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
