oneapi::tbb::concurrent_multiset 完整指南支持并发插入与查找的有序多重集合容器【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldoneapi::tbb::concurrent_multiset是 oneAPI Threading Building BlocksoneTBB提供的线程安全有序关联容器用于表示元素的有序序列。它支持并发的插入、查找与遍历但不支持并发删除操作且允许存储多个等价元素——这一特性使其非常适合在高并发场景下维护带有重复键的有序数据集。阅读本文后你将掌握concurrent_multiset的完整接口、线程安全语义边界、与concurrent_set的差异以及如何在多线程程序中正确使用这一容器。本指南基于当前仓库 third-party/tbb 目录下随附的 oneTBB 官方规范文档concurrent_multiset_cls.rst编写并佐以仓库中的实际源码与测试用例。该 TBB 版本作为第三方库被随本项目mold 链接器一同分发本文内容直接适用于仓库内 third-party/tbb/include/oneapi/tbb/concurrent_set.h 所声明的实现。容器概述什么是 concurrent_multisetconcurrent_multiset是类模板oneapi::tbb::concurrent_multiset的实例表示一个元素的有序序列具有以下核心特征并发插入与查找多个线程可以同时向容器中插入元素也可以同时进行查找与遍历操作不支持并发擦除删除erase类操作被标记为“并发不安全”concurrently unsafe只能在串行环境下调用允许等价元素与std::multiset类似容器中可以存储多个相互等价equivalent的元素这是它与concurrent_set不允许重复的核心区别。在源码层面concurrent_multiset位于命名空间oneapi::tbb中其声明定义在头文件 third-party/tbb/include/oneapi/tbb/concurrent_set.h 内template typename Key, typename Compare std::lessKey, typename Allocator tbb::tbb_allocatorKey class concurrent_multiset;从实现结构看concurrent_set.hconcurrent_set与concurrent_multiset都建立在concurrent_skip_list并发跳跃链表定义于 detail/_concurrent_skip_list.h之上二者通过模板参数AllowMultimapping区分是否允许多重映射。concurrent_multiset对应的set_traits将allow_multimapping置为true这正是其能存放多个等价元素的底层原因。跳跃表 分层节点的结构使得插入与查找可以无锁化并发执行。与标准库 multiset 的对比维度std::multisetconcurrent_multiset线程安全同一容器上的并发写需要外部加锁插入、查找、遍历可安全并发并发删除由外部锁保护不支持擦除操作仅限串行调用迭代器类型BidirectionalIteratorForwardIterator底层结构红黑树并发跳跃链表skip list等价元素允许允许类模板总体结构Class Template Synopsisconcurrent_multiset的完整类模板声明如下头文件oneapi/tbb/concurrent_set.hnamespace oneapi { namespace tbb { template typename T, typename Compare std::lessT, typename Allocator tbb_allocatorT class concurrent_multiset { public: using key_type T; using value_type T; using size_type implementation-defined unsigned integer type; using difference_type implementation-defined signed integer type; using key_compare Compare; using value_compare Compare; using allocator_type Allocator; using reference value_type; using const_reference const value_type; using pointer std::allocator_traitsAllocator::pointer; using const_pointer std::allocator_traitsAllocator::const_pointer; using iterator implementation-defined ForwardIterator; using const_iterator implementation-defined constant ForwardIterator; using node_type implementation-defined node handle; using range_type implementation-defined range; using const_range_type implementation-defined constant node handle; // Construction, destruction, copying concurrent_multiset(); explicit concurrent_multiset( const key_compare comp, const allocator_type alloc allocator_type() ); explicit concurrent_multiset( const allocator_type alloc ); // ...见下文“构造与析构”小节 // Iterators iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; // Size and capacity bool empty() const; size_type size() const; size_type max_size() const; // Concurrently safe modifiers见“并发安全的修改操作” // Concurrently unsafe modifiers见“并发不安全的修改操作” // Lookup见“查找操作” // Observers key_compare key_comp() const; value_compare value_comp() const; // Parallel iteration range_type range(); const_range_type range() const; }; // class concurrent_multiset } // namespace tbb } // namespace oneapi模板参数说明T元素类型同时也是键类型key_type与value_type均为T因为该容器不需要键值分离Compare默认std::lessT比较函数对象类型用于对元素排序与判定等价性Allocator默认tbb_allocatorToneTBB 提供的分配器类型负责节点内存的分配与释放。注意一个细节文档中的const_range_type描述为constant node handle属于规范文档的笔误实际含义与const_iterator一致即只读范围对象仓库实现中对应的成员类型定义以实际代码为准。使用要求Requirements根据规范文档模板参数必须满足表达式std::allocator_traitsAllocator::destroy(m, val)必须是良构的well-formed其中m为Allocator类型对象、val为value_type类型对象具体成员函数可能根据操作类型提出更严格的要求Compare必须满足 ISO C 标准 [alg.sorting] 一节中的Compare要求严格弱序Allocator必须满足 ISO C 标准 [allocator.requirements] 一节中的Allocator要求。构造、析构与拷贝空容器构造concurrent_multiset(); explicit concurrent_multiset( const key_compare comp, const allocator_type alloc allocator_type() ); explicit concurrent_multiset( const allocator_type alloc );构造一个空的concurrent_multiset。若提供参数则使用比较函数对象comp进行所有key_type比较并使用分配器alloc分配内存。从元素序列构造template typename InputIterator concurrent_multiset( InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type alloc allocator_type() ); template typename InputIterator concurrent_multiset( InputIterator first, InputIterator last, const allocator_type alloc allocator_type() );构造包含半开区间[first, last)中所有元素的容器。InputIterator必须满足 ISO C 标准 [input.iterators] 的InputIterator要求。concurrent_multiset( std::initializer_listvalue_type init, const key_compare comp key_compare(), const allocator_type alloc allocator_type() ); concurrent_multiset( std::initializer_listvalue_type init, const allocator_type alloc );这两个初始化列表构造函数分别等价于concurrent_multiset(init.begin(), init.end(), comp, alloc)与concurrent_multiset(init.begin(), init.end(), alloc)。拷贝与移动构造concurrent_multiset( const concurrent_multiset other ); concurrent_multiset( const concurrent_multiset other, const allocator_type alloc );构造other的副本。若未显式提供分配器则通过std::allocator_traitsallocator_type::select_on_container_copy_construction(other.get_allocator())获得。在与other并发操作的情况下行为未定义。concurrent_multiset( concurrent_multiset other ); concurrent_multiset( concurrent_multiset other, const allocator_type alloc );以移动语义构造容器other被置于有效但未指定的状态若未提供分配器则通过std::move(other.get_allocator())获得。同样与other并发操作时行为未定义。析构函数~concurrent_multiset();销毁容器调用所有存储元素的析构函数并释放内存。与*this并发操作时行为未定义。赋值运算符concurrent_multiset operator( const concurrent_multiset other ); concurrent_multiset operator( concurrent_multiset other ); concurrent_multiset operator( std::initializer_listvalue_type init );拷贝赋值将*this中所有元素替换为other中元素的副本若std::allocator_traitsallocator_type::propagate_on_container_copy_assignment::value为true则拷贝赋值分配器移动赋值以移动语义替换元素other处于有效但未指定状态分配器传播规则由propagate_on_container_move_assignment决定初始化列表赋值将元素替换为init中的元素若init中包含多个键等价的元素插入哪一个是不确定的。三者均要求在与*this及other并发操作时行为未定义且均返回*this的引用。迭代器Iteratorsiterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const;begin/cbegin返回指向容器首元素的迭代器end/cend返回指向容器尾后past-the-end元素的迭代器。concurrent_multiset::iterator与concurrent_multiset::const_iterator满足 ISO C 标准 [forward.iterators] 的ForwardIterator要求——注意这比std::multiset的双向迭代器弱一档只能前向遍历不能后退。遍历方向按照元素的有序排列进行因此遍历结果是有序的。容量与大小Size and capacitybool empty() const; size_type size() const; size_type max_size() const;empty()容器为空返回true否则返回falsesize()返回容器中元素的数量max_size()返回容器可容纳的最大元素数量。重要语义empty()与size()的结果在存在挂起的并发插入时可能与容器的实际状态存在差异例如其他线程的插入尚未提交。因此它们更适合用于调试或粗粒度统计而非依赖精确值的同步逻辑。这也是 TBB 并发容器与标准库容器在使用心智上的一个重要差别。并发安全的修改操作Concurrently safe modifiers本节所有成员函数可以彼此并发执行也可以与查找方法及容器遍历并发执行。这正是concurrent_multiset的核心价值所在。插入单个值std::pairiterator, bool insert( const value_type value ); std::pairiterator, bool insert( value_type value );插入值value。返回std::pairiterator, bool其中iterator指向被插入元素布尔值恒为true——因为在 multiset 语义下插入永远不会因重复而失败这一点与concurrent_set的insert可能返回false不同。iterator insert( const_iterator hint, const value_type value ); iterator insert( const_iterator hint, value_type value );带提示位置hint的插入版本hint作为元素应放置位置的“建议”可能用于优化插入性能返回指向被插入元素的迭代器。要求拷贝版本要求value_type满足 [container.requirements] 的CopyInsertable移动版本要求满足MoveInsertable。移动插入后value处于有效但未指定的状态。插入元素序列template typename InputIterator void insert( InputIterator first, InputIterator last ); void insert( std::initializer_listvalue_type init );将半开区间[first, last)中所有元素插入容器后者等价于insert(init.begin(), init.end())。插入节点句柄node handlestd::pairiterator, bool insert( node_type nh ); iterator insert( const_iterator hint, node_type nh );若节点句柄nh为空则什么都不做否则将nh所拥有的节点插入容器插入后nh处于空状态不会调用value_type的拷贝或移动构造函数零拷贝转移若nh非空且get_allocator() ! nh.get_allocator()行为未定义。节点句柄机制允许将元素从容器中“提取”后再插入到另一个容器或其他位置而不发生拷贝是unsafe_extract的配套设施。原位构造元素Emplacetemplate typename... Args std::pairiterator, bool emplace( Args... args ); template typename... Args iterator emplace_hint( const_iterator hint, Args... args );emplace使用args在容器内原位构造元素返回pairiterator, bool布尔值恒为trueemplace_hint额外接受提示位置。要求value_type满足 [container.requirements] 的EmplaceConstructible。原位构造避免了临时对象的拷贝/移动适合构造开销较大的元素类型。合并容器Mergetemplate typename SrcCompare void merge( concurrent_setT, SrcCompare, Allocator source ); template typename SrcCompare void merge( concurrent_setT, SrcCompare, Allocator source ); template typename SrcCompare void merge( concurrent_multisetT, SrcCompare, Allocator source ); template typename SrcCompare void merge( concurrent_multisetT, SrcCompare, Allocator source );将source中所有元素转移到*this不调用value_type的拷贝或移动构造函数节点级转移。若get_allocator() ! source.get_allocator()行为未定义。由于 multiset 不排斥重复元素从concurrent_set或concurrent_multiset合并均可无损完成。从源码看concurrent_set.h这些merge重载最终都调用底层跳跃表的internal_merge实现于 detail/_concurrent_skip_list.h。并发不安全的修改操作Concurrently unsafe modifiers本节所有成员函数只能串行执行若它们与其他方法无论是否并发安全并发执行行为未定义。这是concurrent_multiset最重要的使用边界——删除必须加锁或仅在单线程阶段进行。清空容器void clear();移除容器中所有元素。擦除单个元素iterator unsafe_erase( const_iterator pos ); iterator unsafe_erase( iterator pos );移除pos指向的元素使该元素的所有迭代器与引用失效返回被移除元素的后继迭代器。要求pos有效、可解引用且指向*this中的元素。size_type unsafe_erase( const key_type key );移除所有与key等价的元素若存在返回被移除元素的数量。注意由于 multiset 允许多个等价元素一次调用会删除全部等价元素。透明比较器支持的擦除template typename K size_type unsafe_erase( const K key );移除所有与key等价的元素。仅当以下条件全部成立时参与重载决议key_compare::is_transparent有效且表示一个类型std::is_convertibleK, iterator::value为falsestd::is_convertibleK, const_iterator::value为false。透明比较transparent comparator如std::less允许使用与key_type不同的类型进行查找/删除从而避免构造临时键对象的开销。擦除元素区间iterator unsafe_erase( const_iterator first, const_iterator last );移除半开区间[first, last)内的所有元素返回最后一个被移除元素的后继迭代器。要求该区间是*this中的有效子区间。提取节点句柄node_type unsafe_extract( iterator pos ); node_type unsafe_extract( const_iterator pos ); node_type unsafe_extract( const key_type key ); template typename K node_type unsafe_extract( const K key );将元素的所有权从容器转移到节点句柄按位置提取将pos指向的元素的所有权转移至句柄不调用拷贝/移动构造函数该元素的迭代器失效但指针与引用仍然有效按键提取若存在与key等价的元素则转移其所有权若存在多个等价元素提取哪一个是不确定的找不到时返回空句柄模板重载unsafe_extract(const K)的参与条件与unsafe_erase(const K)相同要求is_transparent。提取后的节点句柄可通过insert(node_type)零拷贝插入到另一个容器要求分配器兼容。交换void swap( concurrent_multiset other );交换*this与other的内容。若std::allocator_traitsallocator_type::propagate_on_container_swap::value为true则交换分配器否则若get_allocator() ! other.get_allocator()行为未定义。查找操作Lookup本节所有方法可以彼此并发执行也可以与并发安全的修改操作及容器遍历并发执行。所有按键查找都基于Compare定义的等价性!(ab) !(ba)进行。size_type count( const key_type key ); template typename K size_type count( const K key );返回与key等价的元素数量。模板重载要求key_compare::is_transparent有效。iterator find( const key_type key ); const_iterator find( const key_type key ) const; template typename K iterator find( const K key ); template typename K const_iterator find( const K key ) const;返回指向与key等价元素的迭代器若不存在则返回end()。若存在多个等价元素返回哪一个是不确定的这是并发容器的典型折中为了无锁高效不保证确定选择。bool contains( const key_type key ) const; template typename K bool contains( const K key ) const;至少存在一个与key等价的元素时返回true否则返回false。适合只关心“是否存在”的场景避免find返回值的判空样板。边界查询lower_bound / upper_bound / equal_rangeiterator lower_bound( const key_type key ); const_iterator lower_bound( const key_type key ) const;返回指向容器中第一个“不小于”not less thankey的元素的迭代器。iterator upper_bound( const key_type key ); const_iterator upper_bound( const key_type key ) const;返回指向容器中第一个“大于”greater thankey的元素的迭代器。std::pairiterator, iterator equal_range( const key_type key ); std::pairconst_iterator, const_iterator equal_range( const key_type key ) const;若至少存在一个与key等价的元素返回{f, l}其中f指向第一个等价元素、l指向最后一个等价元素的后继否则返回{end(), end()}。equal_range是lower_bound与upper_bound的组合可用于遍历某一等价键的全部元素。以上每组方法都提供透明比较重载const K版本参与条件统一为key_compare::is_transparent有效。观察者Observersallocator_type get_allocator() const; key_compare key_comp() const; value_compare value_comp() const;get_allocator()返回与*this关联的分配器的副本key_comp()返回与*this关联的键比较函数对象的副本value_comp()返回用于比较value_type对象的value_compare类对象。由于key_type value_type Tkey_comp与value_comp在此容器中语义等价。并行迭代Parallel iterationrange_type range(); const_range_type range() const;返回表示容器中所有元素的range对象。range_type与const_range_type满足 TBB 规范的ContainerRange要求详见 named_requirements/containers/container_range两者的区别仅在于边界迭代器类型const_range_type使用const_iterator作为边界range_type使用iterator作为边界。range()返回的对象可以配合 TBB 并行算法如parallel_for、parallel_reduce使用容器范围会被自动切分为多个子范围每个子范围由不同线程独立遍历从而实现对整个容器的并行只读遍历。这是concurrent_multiset相比手写锁 std::multiset在吞吐量上的又一优势——遍历本身也并行化了。非成员函数Non-member functions规范文档规定以下函数提供对concurrent_multiset对象的二元比较、字典序比较与交换操作template typename T, typename Compare, typename Allocator void swap( concurrent_multisetT, Compare, Allocator lhs, concurrent_multisetT, Compare, Allocator rhs ); template typename T, typename Compare, typename Allocator bool operator( const concurrent_multisetT, Compare, Allocator lhs, const concurrent_multisetT, Compare, Allocator rhs ); template typename T, typename Compare, typename Allocator bool operator!( const concurrent_multisetT, Compare, Allocator lhs, const concurrent_multisetT, Compare, Allocator rhs ); template typename T, typename Compare, typename Allocator bool operator( const concurrent_multisetT, Compare, Allocator lhs, const concurrent_multisetT, Compare, Allocator rhs ); // operator、operator、operator 类似这些函数定义的确切命名空间未指定只要它们能在相应的比较运算中被使用即可。例如实现可以在内部命名空间中定义类与函数并将oneapi::tbb::concurrent_multiset定义为类型别名使这些非成员函数仅能通过实参依赖查找ADL被找到。仓库实现即遵循此模式在 concurrent_set.h 中swap定义于内部命名空间detail::d3随后通过using detail::d3::concurrent_multiset;将其暴露于oneapi::tbb::v1内联命名空间。推导指引Deduction guides从 C17 起若可能concurrent_multiset的构造函数支持类模板实参推导CTAD。拷贝/移动构造函数含带显式allocator_type参数的版本提供隐式生成的推导指引。此外还提供以下显式推导指引template typename InputIterator, typename Compare std::lessiterator_value_tInputIterator, typename Allocator tbb::tbb_allocatoriterator_value_tInputIterator concurrent_multiset( InputIterator, InputIterator, Compare Compare(), Allocator Allocator() ) - concurrent_multisetiterator_value_tInputIterator, Compare, Allocator; template typename InputIterator, typename Allocator concurrent_multiset( InputIterator, InputIterator, Allocator ) - concurrent_multisetiterator_value_tInputIterator, std::lessiterator_value_tInputIterator, Allocator; template typename Key, typename Compare std::lessKey, typename Allocator tbb::tbb_allocatorKey concurrent_multiset( std::initializer_listKey, Compare Compare(), Allocator Allocator() ) - concurrent_multisetKey, Compare, Allocator; template typename Key, typename Allocator concurrent_multiset( std::initializer_listKey, Allocator ) - concurrent_multisetKey, std::lessKey, Allocator;其中类型别名iterator_value_t定义为template typename InputIterator using iterator_value_t typename std::iterator_traitsInputIterator::value_type;这些推导指引仅在以下条件全部满足时参与重载决议InputIterator满足 [input.iterators] 的 InputIterator 要求Allocator满足 [allocator.requirements] 的 Allocator 要求Compare不满足 Allocator 要求用于消除比较器与分配器参数之间的歧义。官方规范文档给出的示例#include oneapi/tbb/concurrent_set.h #include vector int main() { std::vectorint v; // 推导 cs1 为 concurrent_multisetint oneapi::tbb::concurrent_multiset cs1(v.begin(), v.end()); // 推导 cs2 为 concurrent_multisetint oneapi::tbb::concurrent_multiset cs2({1, 2, 3}); }仓库实现中的推导指引与文档一致见 concurrent_set.h 中__TBB_CPP17_DEDUCTION_GUIDES_PRESENT宏保护下的定义并额外通过std::enable_if_t在编译期校验is_input_iterator_v、is_allocator_v等约束。使用注意事项与最佳实践1. 明确并发安全边界concurrent_multiset的并发安全是有明确界限的可以并发insert含 hint、范围、节点句柄、emplace 系列、merge、全部查找方法、range()遍历必须串行clear、unsafe_erase系列、unsafe_extract系列、swap以及拷贝/移动构造、赋值、析构。一个典型的错误模式是多个工作线程持续insert的同时主线程调用unsafe_erase清理过期数据。这属于未定义行为。正确做法是将删除阶段与插入阶段分离或用外部互斥量保护整个删除操作。2. size() 是近似值由于存在并发插入size()在任意时刻都可能与真实元素数量略有偏差。若需要精确计数应在无并发修改的时间点查询或通过count/equal_range等查找操作获得某个键的精确信息。3. 透明比较器减少临时对象开销将Compare指定为std::less透明比较器并启用is_transparent后find(key)、count(key)、unsafe_erase(key)等可以接受与key_type不同的类型如std::string_view查找std::string元素避免为每次查询构造临时key_type对象在高频查找场景下收益明显。4. 多等价元素的“不确定性”find在存在多个等价元素时不保证返回哪一个unsafe_extract(key)提取哪个等价元素也不确定equal_range则是遍历某一键下全部元素的可靠手段。需要确定性语义时应遍历equal_range结果而不是依赖单个find。5. 利用节点句柄实现零拷贝转移需要频繁在容器间移动元素时优先使用unsafe_extractinsert(node_type)组合或merge全程不触发value_type的拷贝/移动构造避免大对象的深拷贝开销。注意所有相关容器必须使用相同兼容的分配器。与仓库源码和测试的印证声明与实现concurrent_set.h 同时定义concurrent_set与concurrent_multiset二者继承自concurrent_skip_list通过set_traits的allow_multimapping参数区分concurrent_set.h底层跳跃表detail/_concurrent_skip_list.h 实现并发跳跃链表merge的底层转移逻辑为internal_mergedetail/_concurrent_skip_list.h节点层级由geometric_level_generator按几何分布随机生成detail/_concurrent_skip_list.h测试用例仓库中的 conformance_concurrent_set.cpp 同时覆盖concurrent_set与concurrent_multiset规范文件头注释明确标注 Test for [containers.concurrent_set containers.concurrent_multiset] specifications包括成员类型测试、并发插入/查找/遍历的并发正确性验证以及AllowMultimapping对 multiset 的特化std::true_type相关规范文档同名concurrent_set的规范见 concurrent_set_cls.rst二者共享跳跃表实现差异仅在多重映射语义。结语oneapi::tbb::concurrent_multiset为“多线程写入 并发读取 有序遍历”的经典场景提供了一条无外部锁的路径插入、查找与遍历均支持安全并发底层由并发跳跃链表保证代价是删除操作被严格限定为串行执行size()与多等价元素选择带有近似/不确定语义。在实际项目中正确理解这些边界——尤其是“并发安全修改”与“并发不安全修改”的分野——是安全使用该容器的前提配合merge、节点句柄与透明比较器可以在不牺牲并发性能的同时获得接近std::multiset的开发体验。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考