企业官网建设流程全解析

• 并发编程
• 高性能计算

oneapi::tbb::concurrent_set是 oneAPI Threading Building Blocks（oneTBB）提供的有序并发容器，它以跳表（skip list）为底层数据结构，维护一组有序且唯一的元素，支持多线程并发插入、查找与遍历，但不支持并发删除。本文以 concurrent_set_cls.rst 为骨架，系统梳理其类模板声明、构造与赋值、并发安全修饰器、查找接口、非成员函数与推导指引，并结合仓库头文件与一致性测试说明底层实现与使用限制，帮助你安全、高效地在并行程序中选用这一容器。

概览：concurrent_set 是什么

oneapi::tbb::concurrent_set是一个类模板，表示一个有序的唯一元素序列（sorted sequence of unique elements）。它与标准库std::set的接口高度相似，但核心差异在于并发语义：

• 支持并发：插入（insert）、就地构造（emplace）、查找（lookup）与遍历（traversal）可以并发执行；
• 不支持并发删除：擦除（erase）只能串行进行，因此 API 中显式命名为unsafe_erase；
• 有序性：元素按键的严格弱序排列，迭代器遍历得到的是有序序列，适合范围查询（lower_bound/upper_bound/equal_range）。

类模板的完整声明位于头文件<oneapi/tbb/concurrent_set.h>：

namespace oneapi { namespace tbb { template <typename T, typename Compare = std::less<T>, typename Allocator = tbb_allocator<T>> class concurrent_set { /* ... */ }; } }

三个模板参数的含义分别是：

头文件对模板参数还提出一项额外要求：表达式std::allocator_traits<Allocator>::destroy(m, val)（其中m为Allocator类型对象，val为value_type类型对象）必须良构（well-formed），成员函数可依据操作类型提出更严格的要求。

源码级实现：基于并发跳表

从 concurrent_set.h 的源码可以看到，concurrent_set并非独立实现，而是继承自内部模板concurrent_skip_list：

template <typename Key, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<Key>> class concurrent_set : public concurrent_skip_list<set_traits<Key, Compare, geometric_level_generator<32>, Allocator, false>> {

其中：

• set_traits将key_type与value_type都定义为Key（因为 set 中元素本身即键），并设置allow_multimapping = false，这正是"元素唯一"的语义来源；
• geometric_level_generator<32>以几何分布随机生成跳表节点层数，最大层数为 32；
• 同一文件中定义的concurrent_multiset使用AllowMultimapping = true，允许重复元素，与concurrent_set形成对照。

跳表的具体实现在 detail/_concurrent_skip_list.h。这一实现选择意味着：插入与查找的期望复杂度为 O(log n)，且天然适合无锁化的并发更新——这正是它区别于基于红黑树的std::set的关键。上文中提到的range_type也是由该跳表基类定义的（见_concurrent_skip_list.h中的range_type : public const_range_type）。

容器内部类型

类模板 Synopsis 定义了一组与std::set对应内部类型：

using key_type = T; using value_type = T; 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 size_type = <implementation-defined unsigned integer type>; using difference_type = <implementation-defined signed integer type>; 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>;

其中size_type、difference_type、iterator、const_iterator、node_type、range_type等类型为"实现定义"（implementation-defined），具体类型由底层跳表基类确定。iterator与const_iterator必须满足 ISO C++ 标准 [forward.iterators] 的ForwardIterator要求。node_type（节点句柄）用于无拷贝/无移动的节点转移操作。

一致性测试 conformance_concurrent_set.cpp 中的test_member_types用例专门验证了这些成员类型的正确性。

构造、析构与拷贝赋值

空容器构造函数

concurrent_set(); explicit concurrent_set( const key_compare& comp, const allocator_type& alloc = allocator_type() ); explicit concurrent_set( const allocator_type& alloc );

构造一个空的concurrent_set。若提供比较仿函数comp，则所有key_type比较均使用它；若提供分配器alloc，则使用它分配内存。

从元素序列构造

template <typename InputIterator> concurrent_set( InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type() ); template <typename InputIterator> concurrent_set( InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type() );

构造包含半开区间[first, last)内所有元素的concurrent_set。注意：若区间内存在多个相等元素，插入哪一个是不确定的（unspecified）。InputIterator必须满足 [input.iterators] 的要求。

两个std::initializer_list构造函数分别等价于concurrent_set(init.begin(), init.end(), comp, alloc)与concurrent_set(init.begin(), init.end(), alloc)。

拷贝与移动构造

concurrent_set( const concurrent_set& other ); concurrent_set( const concurrent_set& other, const allocator_type& alloc ); concurrent_set( concurrent_set&& other ); concurrent_set( concurrent_set&& other, const allocator_type& alloc );

• 拷贝构造：若未提供分配器参数，通过std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.get_allocator())获取；与other上的并发操作行为未定义。
• 移动构造：other被置于合法但未指定的状态（valid, but unspecified state）；若未提供分配器参数，通过std::move(other.get_allocator())获取；与other上的并发操作行为未定义。

析构函数

~concurrent_set();

销毁容器，调用存储元素的析构函数并释放存储空间。与*this上的并发操作行为未定义。

赋值运算符

concurrent_set& operator=( const concurrent_set& other ); concurrent_set& operator=( concurrent_set&& other ); concurrent_set& operator=( std::initializer_list<value_type> init );

• 拷贝赋值：以other中元素的副本替换*this全部元素；当std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value为true时拷贝赋值分配器；与*this或other上的并发操作行为未定义。
• 移动赋值：以移动语义用other的元素替换*this；other处于合法但未指定状态；分配器传播规则同上。
• initializer_list赋值：以init的元素替换*this全部元素；若init含多个相等键元素，插入哪个不确定；与*this上的并发操作行为未定义。

三者均返回*this的引用。从源码看，concurrent_set在 concurrent_set.h 中显式 default 了拷贝/移动构造与赋值（rule of 5），并单独实现了initializer_list赋值运算符。

迭代器

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）的迭代器。

iterator与const_iterator满足ForwardIterator要求，遍历结果即按Compare排序的有序序列。所有查找方法与并发安全修饰器可在遍历期间并发执行。

容量查询

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

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

文档明确指出：empty()与size()的结果可能因存在挂起的并发插入而与容器实际状态不一致（The result may differ from the actual container state in case of pending concurrent insertions），因此这两个接口仅适合作为近似/参考值，不能作为并发同步的依据。

并发安全修饰器（Concurrently Safe Modifiers）

本节所有成员函数可相互并发执行，也可与查找方法及容器遍历并发执行，是concurrent_set并发能力的核心。

插入值

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

• insert(value)：尝试把value插入容器。返回std::pair<iterator, bool>：iterator指向新插入元素或已有等键元素；布尔值为true表示插入发生，false表示已存在等键元素（未插入）。
• insert(hint, value)：hint仅作为放置位置的建议，返回指向插入元素或等键已有元素的迭代器。
• 拷贝版要求value_type满足CopyInsertable，移动版要求满足MoveInsertable，且移动后value处于合法但未指定状态。

插入元素序列

template <typename InputIterator> void insert( InputIterator first, InputIterator last ); void insert( std::initializer_list<value_type> init );

尝试把区间[first, last)（或init）内所有元素插入容器。若区间内含多个相等元素，插入哪个不确定。后者等价于insert(init.begin(), init.end())。

插入节点句柄

std::pair<iterator, bool> insert( node_type&& nh ); iterator insert( const_iterator hint, node_type&& nh );

• 若nh为空句柄，什么都不做；
• 否则尝试插入nh拥有的节点；不执行value_type的任何拷贝/移动构造；
• 插入失败时nh继续持有节点；成功时nh被置空；
• 若nh非空且get_allocator() != nh.get_allocator()，行为未定义；
• 返回值语义与普通 insert 一致，比较基准是nh.value()。

node_type通常来自unsafe_extract，二者配合可实现免拷贝的节点转移。

就地构造（Emplace）

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

尝试用args就地构造元素并插入。返回语义同insert。要求value_type满足EmplaceConstructible。

合并容器

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中键在目标容器中不存在的元素转移过来（即只转移"不冲突"的元素）。若源容器含多个相等元素，转移哪个不确定。不执行value_type的拷贝/移动构造。若get_allocator() != source.get_allocator()，行为未定义。SrcCompare允许源容器使用不同比较器。

源码中，concurrent_set的merge直接调用基类的internal_merge（见 concurrent_set.h），concurrent_multiset同样支持参与合并。

并发不安全修饰器（Concurrently Unsafe Modifiers）

本节所有成员函数只能串行执行；若与其他方法（包括并发安全方法）并发执行，行为未定义。这正是"不支持并发擦除"的体现，也因此所有擦除接口都以unsafe_前缀命名，提醒调用者其串行约束。

清空与擦除

void clear(); iterator unsafe_erase( const_iterator pos ); iterator unsafe_erase( iterator pos ); iterator unsafe_erase( const_iterator first, const_iterator last ); size_type unsafe_erase( const key_type& key ); template <typename K> size_type unsafe_erase( const K& key );

• clear()：移除全部元素。
• unsafe_erase(pos)：移除pos指向的元素，使指向被删元素的所有迭代器与引用失效，返回被删元素之后的迭代器。要求pos有效、可解引用且指向*this中的元素。
• unsafe_erase(first, last)：移除半开区间[first, last)内的全部元素，返回最后一个被删元素之后的迭代器。要求该区间是*this中的合法子区间。
• unsafe_erase(key)：若存在与key等价的元素则移除之，返回1；否则返回0。

提取节点

node_type unsafe_extract( const_iterator pos ); node_type unsafe_extract( iterator pos ); node_type unsafe_extract( const key_type& key ); template <typename K> node_type unsafe_extract( const K& key );

把pos指向（或与key等价）的元素所有权转移到节点句柄。不执行value_type的拷贝/移动构造；指向被提取元素的迭代器失效，但指针与引用仍然有效。按键版本若找不到元素则返回空句柄。

透明比较重载（Heterogeneous Lookup）

文档反复出现的模板版本template <typename K> ...（如unsafe_erase、unsafe_extract）是透明比较重载，仅在以下条件全部成立时参与重载决议：

1. 限定名key_compare::is_transparent有效且表示一个类型（即比较器是std::less<void>这类透明比较器）；
2. std::is_convertible<K, iterator>::value为false；
3. std::is_convertible<K, const_iterator>::value为false。

启用后，可以直接用与键不同类型（但可比）的 K 进行查找，避免临时构造key_type。一致性测试中的heterogeneous overloads用例（见 conformance_concurrent_set.cpp）专门验证了这一组接口。

swap

void swap( concurrent_set& other );

交换*this与other的内容。若std::allocator_traits<allocator_type>::propagate_on_container_swap::value为true则交换分配器；否则若get_allocator() != other.get_allocator()，行为未定义。

查找（Lookup）

本节所有方法可相互并发执行，也可与并发安全修饰器及遍历并发执行。

其中find、contains、count提供const版本；lower_bound、upper_bound、equal_range提供const版本。所有方法均提供template <typename K>透明版本，其参与重载决议的条件与上文一致（key_compare::is_transparent有效且表示类型）。由于concurrent_set元素唯一，equal_range返回的区间至多包含一个元素，f指向该元素、l为其后继。

观察器（Observers）

allocator_type get_allocator() const; key_compare key_comp() const; value_compare value_comp() const;

• get_allocator()：返回与*this关联的分配器的副本；
• key_comp()：返回键比较仿函数的副本；
• value_comp()：返回用于比较value_type对象的value_compare对象。

由于 set 的键即值，key_compare与value_compare是同一类型（源码中set_traits::value_compare = compare_type，见 concurrent_set.h）。

并行迭代（Parallel Iteration）

range_type range(); const_range_type range() const;

range_type与const_range_type满足 oneTBB 文档中的ContainerRange要求（见 container_range 章节）。二者的差异仅在于边界迭代器类型：range_type使用concurrent_set::iterator，const_range_type使用concurrent_set::const_iterator。range()返回表示容器全部元素的范围对象。

range()的设计目标是配合 oneTBB 并行算法（如parallel_for）对容器进行并发安全的分块遍历——这是concurrent_set有别于普通std::set的重要扩展能力。

非成员函数

非成员函数提供交换、二元比较与字典序比较。文档特别说明：这些函数的确切定义命名空间未指定，只要能在相应比较运算中通过实参依赖查找（ADL）被使用即可；例如实现可把类与函数定义在同一内部命名空间，并将oneapi::tbb::concurrent_set定义为类型别名，使非成员函数仅能经 ADL 触达。

swap

template <typename T, typename Compare, typename Allocator> void swap( concurrent_set<T, Compare, Allocator>& lhs, concurrent_set<T, Compare, Allocator>& rhs );

等价于lhs.swap(rhs)。

二元比较

两个concurrent_set相等当且仅当元素个数相同，且每个位置上（按序遍历）的对应元素相等：

bool operator==( const concurrent_set& lhs, const concurrent_set& rhs ); bool operator!=( const concurrent_set& lhs, const concurrent_set& rhs );

字典序比较

bool operator<( const concurrent_set& lhs, const concurrent_set& rhs ); bool operator<=( const concurrent_set& lhs, const concurrent_set& rhs ); bool operator>( const concurrent_set& lhs, const concurrent_set& rhs ); bool operator>=( const concurrent_set& lhs, const concurrent_set& rhs );

四个运算符分别按字典序判断lhs小于 / 小于等于 / 大于 / 大于等于rhs。一致性测试的test_set_comparisons用例（见 conformance_concurrent_set.cpp）覆盖了这些比较运算符。

推导指引（Deduction Guides，C++17 起）

只要可行，concurrent_set构造函数支持类模板实参推导（CTAD）。拷贝/移动构造函数（含带显式allocator_type参数的版本）提供隐式生成的推导指引，此外还提供如下显式推导指引：

template <typename InputIterator, typename Compare = std::less<iterator_value_t<InputIterator>>, typename Allocator = tbb::tbb_allocator<iterator_value_t<InputIterator>>> concurrent_set( InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator() ) -> concurrent_set<iterator_value_t<InputIterator>, Compare, Allocator>; template <typename InputIterator, typename Allocator> concurrent_set( InputIterator, InputIterator, Allocator ) -> concurrent_set<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_set( std::initializer_list<Key>, Compare = Compare(), Allocator = Allocator() ) -> concurrent_set<Key, Compare, Allocator>; template <typename Key, typename Allocator> concurrent_set( std::initializer_list<Key>, Allocator ) -> concurrent_set<Key, std::less<Key>, Allocator>;

其中类型别名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; // Deduces cs1 as concurrent_set<int> oneapi::tbb::concurrent_set cs1(v.begin(), v.end()); // Deduces cs2 as concurrent_set<int> oneapi::tbb::concurrent_set cs2({1, 2, 3}); }

一致性测试的CTAD support in concurrent_set用例（见 conformance_concurrent_set.cpp）验证了推导指引行为。

典型使用模式与注意事项

综合以上接口，可以归纳出concurrent_set的典型使用模式与关键注意事项：

1. 生产者-消费者式的集合构建：多个线程同时向容器insert/emplace元素，构建完成后串行调用unsafe_erase或clear清理，或利用range()+parallel_for做并行遍历。
2. 节点免拷贝转移：先用unsafe_extract取出节点（串行阶段），再在并发阶段用insert(node_type&&)转移，全程不触发value_type的拷贝/移动构造，适合管理不可拷贝或拷贝昂贵的元素。
3. 透明查找避免临时对象：当比较器支持透明比较（如std::less<>）时，用异构键直接调用find/contains/count/lower_bound/upper_bound/equal_range，省去临时key_type的构造。
4. 内存与分配器一致性：涉及节点转移（insert(node_type&&)、merge）与swap的操作对分配器一致性有硬性约束（不一致时行为未定义），务必保证参与方分配器相同。
5. 并发语义边界：size()/empty()在挂起并发插入时可能与实际状态不一致；拷贝/移动/赋值/析构/擦除期间的并发操作行为未定义；只有"并发安全修饰器 + 查找 + 遍历"这三类操作可以自由并发。

concurrent_set的完整参考文档位于 concurrent_set_cls.rst，其姊妹容器concurrent_multiset（允许重复元素）的文档见 concurrent_multiset_cls.rst，无序并发集合可参考 concurrent_unordered_set_cls.rst。若需要在共享内存高并发场景下做基于值的快速去重与排序访问，concurrent_set是一个与 oneTBB 任务调度模型天然契合的选择。

• 并发编程
• 高性能计算