企业官网建设流程全解析

oneapi::tbb::concurrent_multiset 完整指南：支持并发插入与查找的有序多重集合容器

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

oneapi::tbb::concurrent_multiset是 oneAPI Threading Building Blocks（oneTBB）提供的线程安全有序关联容器，用于表示元素的有序序列。它支持并发的插入、查找与遍历，但不支持并发删除操作，且允许存储多个等价元素——这一特性使其非常适合在高并发场景下维护带有重复键的有序数据集。阅读本文后，你将掌握concurrent_multiset的完整接口、线程安全语义边界、与concurrent_set的差异，以及如何在多线程程序中正确使用这一容器。

本指南基于当前仓库 third-party/tbb 目录下随附的 oneTBB 官方规范文档（concurrent_multiset_cls.rst）编写，并佐以仓库中的实际源码与测试用例。该 TBB 版本作为第三方库被随本项目（mold 链接器）一同分发，本文内容直接适用于仓库内 third-party/tbb/include/oneapi/tbb/concurrent_set.h 所声明的实现。

容器概述：什么是 concurrent_multiset

concurrent_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::less<Key>, typename Allocator = tbb::tbb_allocator<Key>> class concurrent_multiset;

从实现结构看（concurrent_set.h），concurrent_set与concurrent_multiset都建立在concurrent_skip_list（并发跳跃链表，定义于 detail/_concurrent_skip_list.h）之上，二者通过模板参数AllowMultimapping区分是否允许多重映射。concurrent_multiset对应的set_traits将allow_multimapping置为true，这正是其能存放多个等价元素的底层原因。跳跃表 + 分层节点的结构使得插入与查找可以无锁化并发执行。

与标准库 multiset 的对比

类模板总体结构（Class Template Synopsis）

concurrent_multiset的完整类模板声明如下（头文件<oneapi/tbb/concurrent_set.h>）：

namespace oneapi { namespace tbb { template <typename T, typename Compare = std::less<T>, typename Allocator = tbb_allocator<T>> 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_traits<Allocator>::pointer; using const_pointer = std::allocator_traits<Allocator>::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::less<T>）：比较函数对象类型，用于对元素排序与判定等价性；
• Allocator（默认tbb_allocator<T>）：oneTBB 提供的分配器类型，负责节点内存的分配与释放。

注意一个细节：文档中的const_range_type描述为"constant node handle"，属于规范文档的笔误，实际含义与const_iterator一致（即只读范围对象），仓库实现中对应的成员类型定义以实际代码为准。

使用要求（Requirements）

根据规范文档，模板参数必须满足：

1. 表达式std::allocator_traits<Allocator>::destroy(m, val)必须是良构的（well-formed），其中m为Allocator类型对象、val为value_type类型对象；具体成员函数可能根据操作类型提出更严格的要求；
2. Compare必须满足 ISO C++ 标准 [alg.sorting] 一节中的Compare要求（严格弱序）；
3. 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_list<value_type> init, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type() ); concurrent_multiset( std::initializer_list<value_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_traits<allocator_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_list<value_type> init );

• 拷贝赋值：将*this中所有元素替换为other中元素的副本；若std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value为true则拷贝赋值分配器；
• 移动赋值：以移动语义替换元素，other处于有效但未指定状态；分配器传播规则由propagate_on_container_move_assignment决定；
• 初始化列表赋值：将元素替换为init中的元素；若init中包含多个键等价的元素，插入哪一个是不确定的。

三者均要求在与*this（及other）并发操作时行为未定义，且均返回*this的引用。

迭代器（Iterators）

iterator 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 capacity）

bool empty() const; size_type size() const; size_type max_size() const;

• empty()：容器为空返回true，否则返回false；
• size()：返回容器中元素的数量；
• max_size()：返回容器可容纳的最大元素数量。

重要语义：empty()与size()的结果在存在挂起的并发插入时，可能与容器的实际状态存在差异（例如其他线程的插入尚未提交）。因此它们更适合用于调试或粗粒度统计，而非依赖精确值的同步逻辑。这也是 TBB 并发容器与标准库容器在使用心智上的一个重要差别。

并发安全的修改操作（Concurrently safe modifiers）

本节所有成员函数可以彼此并发执行，也可以与查找方法及容器遍历并发执行。这正是concurrent_multiset的核心价值所在。

插入单个值

std::pair<iterator, bool> insert( const value_type& value ); std::pair<iterator, bool> insert( value_type&& value );

插入值value。返回std::pair<iterator, 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_list<value_type> init );

将半开区间[first, last)中所有元素插入容器；后者等价于insert(init.begin(), init.end())。

插入节点句柄（node handle）

std::pair<iterator, 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的配套设施。

原位构造元素（Emplace）

template <typename... Args> std::pair<iterator, bool> emplace( Args&&... args ); template <typename... Args> iterator emplace_hint( const_iterator hint, Args&&... args );

emplace使用args在容器内原位构造元素，返回pair<iterator, bool>（布尔值恒为true）；emplace_hint额外接受提示位置。要求value_type满足 [container.requirements] 的EmplaceConstructible。原位构造避免了临时对象的拷贝/移动，适合构造开销较大的元素类型。

合并容器（Merge）

template <typename SrcCompare> void merge( concurrent_set<T, SrcCompare, Allocator>& source ); template <typename SrcCompare> void merge( concurrent_set<T, SrcCompare, Allocator>&& source ); template <typename SrcCompare> void merge( concurrent_multiset<T, SrcCompare, Allocator>& source ); template <typename SrcCompare> void merge( concurrent_multiset<T, 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_convertible<K, iterator>::value为false；
• std::is_convertible<K, 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_traits<allocator_type>::propagate_on_container_swap::value为true则交换分配器；否则，若get_allocator() != other.get_allocator()，行为未定义。

查找操作（Lookup）

本节所有方法可以彼此并发执行，也可以与并发安全的修改操作及容器遍历并发执行。所有按键查找都基于Compare定义的等价性（!(a<b) && !(b<a)）进行。

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_range

iterator lower_bound( const key_type& key ); const_iterator lower_bound( const key_type& key ) const;

返回指向容器中第一个“不小于”（not less than）key的元素的迭代器。

iterator upper_bound( const key_type& key ); const_iterator upper_bound( const key_type& key ) const;

返回指向容器中第一个“大于”（greater than）key的元素的迭代器。

std::pair<iterator, iterator> equal_range( const key_type& key ); std::pair<const_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有效。

观察者（Observers）

allocator_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 == T，key_comp与value_comp在此容器中语义等价。

并行迭代（Parallel iteration）

range_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_multiset<T, Compare, Allocator>& lhs, concurrent_multiset<T, Compare, Allocator>& rhs ); template <typename T, typename Compare, typename Allocator> bool operator==( const concurrent_multiset<T, Compare, Allocator>& lhs, const concurrent_multiset<T, Compare, Allocator>& rhs ); template <typename T, typename Compare, typename Allocator> bool operator!=( const concurrent_multiset<T, Compare, Allocator>& lhs, const concurrent_multiset<T, Compare, Allocator>& rhs ); template <typename T, typename Compare, typename Allocator> bool operator<( const concurrent_multiset<T, Compare, Allocator>& lhs, const concurrent_multiset<T, 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）

从 C++17 起，若可能，concurrent_multiset的构造函数支持类模板实参推导（CTAD）。拷贝/移动构造函数（含带显式allocator_type参数的版本）提供隐式生成的推导指引。此外还提供以下显式推导指引：

template <typename InputIterator, typename Compare = std::less<iterator_value_t<InputIterator>>, typename Allocator = tbb::tbb_allocator<iterator_value_t<InputIterator>>> concurrent_multiset( InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator() ) -> concurrent_multiset<iterator_value_t<InputIterator>, Compare, Allocator>; template <typename InputIterator, typename Allocator> concurrent_multiset( InputIterator, InputIterator, Allocator ) -> concurrent_multiset<iterator_value_t<InputIterator>, std::less<iterator_value_t<InputIterator>>, Allocator>; template <typename Key, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<Key>> concurrent_multiset( std::initializer_list<Key>, Compare = Compare(), Allocator = Allocator() ) -> concurrent_multiset<Key, Compare, Allocator>; template <typename Key, typename Allocator> concurrent_multiset( std::initializer_list<Key>, Allocator ) -> concurrent_multiset<Key, std::less<Key>, Allocator>;

其中类型别名iterator_value_t定义为：

template <typename InputIterator> using iterator_value_t = typename std::iterator_traits<InputIterator>::value_type;

这些推导指引仅在以下条件全部满足时参与重载决议：

• InputIterator满足 [input.iterators] 的 InputIterator 要求；
• Allocator满足 [allocator.requirements] 的 Allocator 要求；
• Compare不满足 Allocator 要求（用于消除比较器与分配器参数之间的歧义）。

官方规范文档给出的示例：

#include <oneapi/tbb/concurrent_set.h> #include <vector> int main() { std::vector<int> v; // 推导 cs1 为 concurrent_multiset<int> oneapi::tbb::concurrent_multiset cs1(v.begin(), v.end()); // 推导 cs2 为 concurrent_multiset<int> 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_extract+insert(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_merge（detail/_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