企业官网建设流程全解析

mold 内嵌 TBB：concurrent_unordered_multiset 的构造、析构与复制语义深度解析

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

本文聚焦 mold 仓库 third-party 目录中随附的 Intel oneAPI TBB 规范文档construction_destruction_copying.rst，系统讲解concurrent_unordered_multiset容器从空构造、序列构造、拷贝/移动到析构与赋值运算符的完整生命周期 API。读完本文，你既能掌握规范中每个构造函数与赋值运算符的签名、参数约束与并发安全边界，也能对照 vendored TBB 的模板源码（concurrent_unordered_set.h与内部基类_concurrent_unordered_base.h）理解这些语义背后的无锁实现细节：分片段表、split-ordered 链表、分配器传播规则以及 noexcept 规格的推导方式。

需要说明的前提：mold 是 ELF 链接器，TBB 以第三方依赖形式 vendored 在 third-party/tbb 子树中。本文所有规范依据均出自 construction_destruction_copying.rst，所有实现依据均可在该子树的include/oneapi/tbb头文件与test目录中找到对应物。

一、容器定位：multiset 在 TBB 无序容器家族中的角色

concurrent_unordered_multiset的规范位于 concurrent_unordered_multiset_cls 目录，同目录还包含 bucket 接口、查找、观察器、并行迭代等章节。其类模板声明在 concurrent_unordered_set.h：

template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<Key>> class concurrent_unordered_multiset : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>>

从源码结构看，TBB 的四种无序容器（set/multiset/map/multimap）共用同一个内部基类concurrent_unordered_base<Traits>，差异被压缩进 traits 的一个布尔量allow_multimapping（concurrent_unordered_set.h#L28-L39）：multiset 传true，set 传false。这直接决定了重复键的插入行为——基类在search_after中只有当allow_multimapping为false时才把"找到等键节点"视为插入失败（_concurrent_unordered_base.h#L1022-L1039）。因此本文讨论的构造语义对 set 同样成立，但 multiset 允许等键元素共存于同一桶内。

multiset 类体本身非常薄：除merge与operator=(std::initializer_list)外，其余成员全部继承自基类：

// concurrent_unordered_set.h L208-L219 using base_type::base_type; // 继承基类全部构造函数 concurrent_unordered_multiset() = default; concurrent_unordered_multiset( const concurrent_unordered_multiset& ) = default; concurrent_unordered_multiset( const concurrent_unordered_multiset& other, const allocator_type& alloc ) : base_type(other, alloc) {} concurrent_unordered_multiset( concurrent_unordered_multiset&& ) = default; concurrent_unordered_multiset( concurrent_unordered_multiset&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {} // Required to respect the rule of 5 concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset& ) = default; concurrent_unordered_multiset& operator=( concurrent_unordered_multiset&& ) = default;

源码注释明确写出 default 成员是为了"遵守规则五（rule of 5）"并支撑隐式推导指南。下面按规范文档的小节顺序逐一展开。

二、空容器构造函数

规范给出两组空容器构造（见 construction_destruction_copying.rst#L9-L41）：

concurrent_unordered_multiset(); explicit concurrent_unordered_multiset( const allocator_type& alloc );

构造一个空容器，初始桶数由实现定义（unspecified）；提供alloc时用它分配内存。

explicit concurrent_unordered_multiset( size_type bucket_count, const hasher& hash = hasher(), const key_equal& equal = key_equal(), const allocator_type& alloc = allocator_type() ); concurrent_unordered_multiset( size_type bucket_count, const allocator_type& alloc ); concurrent_unordered_multiset( size_type bucket_count, const hasher& hash, const allocator_type& alloc );

构造一个拥有bucket_count个桶的空容器；可选提供哈希函数、等值谓词与分配器。

"实现定义"的默认桶数在源码中是有确切值的。基类主构造函数（_concurrent_unordered_base.h#L244-L262）：

explicit concurrent_unordered_base( size_type bucket_count, const hasher& hash = hasher(), const key_equal& equal = key_equal(), const allocator_type& alloc = allocator_type() ) : my_size(0), my_bucket_count(round_up_to_power_of_two(bucket_count)), my_max_load_factor(float(initial_max_load_factor)), my_hash_compare(hash, equal), my_head(sokey_type(0)), my_segments(alloc) {} concurrent_unordered_base() : concurrent_unordered_base(initial_bucket_count) {}

对应的实现常量（L787-L788）：

static constexpr size_type initial_bucket_count = 8; static constexpr float initial_max_load_factor = 4; // TODO: consider 1?

即不传参数时初始桶数为 8、初始最大负载因子为 4.0。这里有两个值得注意的实现细节：

1. 桶数会被上取整到 2 的幂。round_up_to_power_of_two（L235-L237）先对bucket_count做log2(x*2-1)再左移一位，例如传 100 会得到 128 个桶。这与桶下标用hash % bucket_count计算（prepare_bucket，L1082-L1085）相配合，保证取模运算可退化为位与。
2. 桶并不在构造时实体分配。my_segments是内嵌段表（embedded segment table），桶 0 直接指向容器内嵌的头节点my_head（见init_bucket中my_segments[0].compare_exchange_strong(disabled, &my_head)，L1095-L1119）；其余桶的虚节点（dummy node）在首次访问时按需插入链表。因此"空构造 + 指定大 bucket_count"的开销非常小，内存占用随实际插入量惰性增长。

另一个结构性事实：my_head(sokey_type(0))表明头节点的 order key 是 0，而普通节点 order key 的最低位恒为 1（split_order_key_regular，L1445-L1453），is_dummy()正是靠这个最低位区分空桶虚节点与真实元素节点（L142-L145）——这是理解拷贝/移动为何要"逐节点复制"的前提。

三、从元素序列构造

规范给出三组迭代器构造、三组初始化列表构造（construction_destruction_copying.rst#L42-L101）：

template <typename InputIterator> concurrent_unordered_multiset( InputIterator first, InputIterator last, size_type bucket_count = /*implementation-defined*/, const hasher& hash = hasher(), const key_equal& equal = key_equal(), const allocator_type& alloc = allocator_type() ); template <typename InputIterator> concurrent_unordered_multiset( InputIterator first, InputIterator last, size_type bucket_count, const allocator_type& alloc ); template <typename InputIterator> concurrent_unordered_multiset( InputIterator first, InputIterator last, size_type bucket_count, const hasher& hash, const allocator_type& alloc );

构造包含半开区间[first, last)中元素的容器。要求：InputIterator必须满足 ISO C++ 标准 [input.iterators] 一节对 InputIterator 的要求。

concurrent_unordered_multiset( std::initializer_list<value_type> init, size_type bucket_count = /*implementation-defined*/, const hasher& hash = hasher(), const key_equal& equal = key_equal(), const allocator_type& alloc = allocator_type() ); // 等价于 concurrent_unordered_multiset(init.begin(), init.end(), bucket_count, hash, equal, alloc) concurrent_unordered_multiset( std::initializer_list<value_type> init, size_type bucket_count, const allocator_type& alloc ); // 等价于 concurrent_unordered_multiset(init.begin(), init.end(), bucket_count, alloc) concurrent_unordered_multiset( std::initializer_list<value_type> init, size_type bucket_count, const hasher& hash, const allocator_type& alloc ); // 等价于 concurrent_unordered_multiset(init.begin(), init.end(), bucket_count, hash, alloc)

源码中迭代器构造的实现（_concurrent_unordered_base.h#L264-L281）就是"先按bucket_count完成基础构造，再循环insert"：

template <typename InputIterator> concurrent_unordered_base( InputIterator first, InputIterator last, size_type bucket_count = initial_bucket_count, const hasher& hash = hasher(), const key_equal& equal = key_equal(), const allocator_type& alloc = allocator_type() ) : concurrent_unordered_base(bucket_count, hash, equal, alloc) { insert(first, last); }

其中insert(first, last)是逐个insert(*first)（L433-L438），每次插入走完整的internal_insert无锁路径（L986-L1017）：计算 order key、经search_after定位、用try_insert的 CAS 循环挂接，插入成功后my_size.fetch_add(1)并按需把桶数翻倍（adjust_table_size，L1041-L1047）。对 multiset 而言，重复键会各自成为独立节点被插入；对 set 则重复键会创建节点后在发现已存在时销毁该节点（internal_insert_value中的destroy_node(insert_result.remaining_node)，L952-L970）。

初始化列表构造则是纯委托：

concurrent_unordered_base( std::initializer_list<value_type> init, size_type bucket_count = initial_bucket_count, const hasher& hash = hasher(), const key_equal& equal = key_equal(), const allocator_type& alloc = allocator_type() ) : concurrent_unordered_base(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}

与规范"等价于……"的表述逐字对应（L336-L348）。

C++17 类模板参数推导

上述构造在 C++17 下支持 CTAD：拷贝/移动构造（含带 allocator 的版本）提供隐式生成的推导指南，头文件另外给出了显式推导指南（规范见 deduction_guides.rst，实现见 concurrent_unordered_set.h#L247 起）。关键约束是：推导指南仅当迭代器满足 InputIterator 要求、allocator 满足 Allocator 要求、且Hash/KeyEqual不满足 Allocator 要求时才参与重载决议——这一组enable_if条件（is_input_iterator_v/is_allocator_v/!std::is_integral_v<Hash>）用于消除"第三个参数是 allocator 还是哈希函数"的二义性。规范给出的示例：

#include <oneapi/tbb/concurrent_unordered_set.h> #include <vector> #include <functional> struct CustomHasher {...}; int main() { std::vector<int> v; // Deduces s1 as concurrent_unordered_multiset<int> oneapi::tbb::concurrent_unordered_multiset s1(v.begin(), v.end()); // Deduces s2 as concurrent_unordered_multiset<int, CustomHasher>; oneapi::tbb::concurrent_unordered_multiset s2(v.begin(), v.end(), CustomHasher{}); }

四、拷贝构造：逐节点复制 split-ordered 链表

规范（construction_destruction_copying.rst#L103-L118）：

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

构造other的拷贝。未提供 allocator 时，调用std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.get_allocator())获得。与other并发操作时行为未定义。

multiset 头文件中这两个构造要么是= default（继承基类），要么显式委托base_type(other, alloc)（concurrent_unordered_set.h#L213-L214）。基类的拷贝构造（_concurrent_unordered_base.h#L283-L311）分三步：

1. 以 relaxed 序快照other的my_size、my_bucket_count、my_max_load_factor、哈希比较器与头节点 order key，并拷贝/带 allocator 拷贝my_segments段表；
2. internal_copy(other)遍历other.my_head.next()开始的整条split-ordered 链表：真实节点用create_node(order_key, value)复制值，虚节点用create_dummy_node(order_key)复制桶锚点，并同步写回my_segments[reverse_bits(order_key)]；
3. 异常安全：try_call(...).on_exception([&] { clear(); })，复制中途抛异常时清理已建节点。

void internal_copy( const concurrent_unordered_base& other ) { node_ptr last_node = &my_head; my_segments[0].store(&my_head, std::memory_order_relaxed); for (node_ptr node = other.my_head.next(); node != nullptr; node = node->next()) { node_ptr new_node; if (!node->is_dummy()) { new_node = create_node(node->order_key(), static_cast<value_node_ptr>(node)->value()); } else { new_node = create_dummy_node(node->order_key()); my_segments[reverse_bits(node->order_key())].store(new_node, std::memory_order_relaxed); } last_node->set_next(new_node); last_node = new_node; } }

（L1321-L1339）

从源码结构看，这份实现把"顺序一致"作为不变量整体迁移：order key（即反向哈希）随节点一起复制，段表与链表的相对关系不变，因此拷贝出的容器可以直接并发使用，而不需要重新哈希。代价是连尚未被任何元素占用的桶虚节点也一并复制——这也是拷贝构造比"迭代 + insert"重建更忠实于other桶布局的原因。

五、移动构造：偷换链表头 vs. 逐节点搬移

规范（construction_destruction_copying.rst#L120-L136）：

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

以移动语义构造，other被留在有效但未指定的状态；未提供 allocator 时由std::move(other.get_allocator())获得；与other并发操作时行为未定义。

基类移动构造（L313-L334）先把my_size、my_bucket_count、负载因子、哈希比较器、my_segments从other搬走，再进入move_content：

void move_content( concurrent_unordered_base&& other ) { // NOTE: allocators should be equal my_head.set_next(other.my_head.next()); other.my_head.set_next(nullptr); my_segments[0].store(&my_head, std::memory_order_relaxed); other.my_bucket_count.store(initial_bucket_count, std::memory_order_relaxed); other.my_max_load_factor = initial_max_load_factor; other.my_size.store(0, std::memory_order_relaxed); }

（L1362-L1371）

这里印证了"valid but unspecified"的规范措辞：move_content直接把other的头节点 next 指针摘走并置空，然后把other的桶数/负载因子/size 重置为初始值（8 桶、4.0、0 元素）——other确实回到与默认构造几乎一致的可复用状态。若两侧 allocator 恒等（is_always_equal，如std::allocator/tbb_allocator），走上述 O(1) 的指针交接。

若 allocator 可能不等，则委托internal_move_construct_with_allocator（L1373-L1391）：分配器相等仍走move_content；不相等则逐节点create_node(order_key, std::move(value))重新构造到alloc中（internal_move，L1341-L1360），并以try_call/on_exception(clear)提供异常安全。

六、析构函数：销毁元素并归还存储

规范（construction_destruction_copying.rst#L138-L148）：

~concurrent_unordered_multiset();

销毁容器：调用被存元素的析构函数并释放所占用的存储。与*this并发操作时行为未定义。

基类析构（L350-L352）一行委托给internal_clear，后者与clear()共用同一段逻辑（L900-L915）：

void internal_clear() { node_ptr next = my_head.next(); node_ptr curr = next; my_head.set_next(nullptr); while (curr != nullptr) { next = curr->next(); destroy_node(curr); curr = next; } my_size.store(0, std::memory_order_relaxed); my_segments.clear(); }

destroy_node（L917-L938）按节点类型分派：虚节点用 rebind 出的node_allocator_type销毁并释放；真实节点先对storage()内的值调用析构（value_node_allocator_traits::destroy），再销毁节点对象本身并释放内存。my_segments.clear()释放段表中各虚节点段。这解释了规范"调用元素析构 + 释放存储"这句话在实现层的两个动作边界：值的析构与节点/段内存的释放是独立步骤。

七、赋值运算符

规范给出三个赋值（construction_destruction_copying.rst#L150-L201）。

拷贝赋值

concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset& other );

以other的元素拷贝替换*this的全部元素；当propagate_on_container_copy_assignment::value为 true 时拷贝赋值 allocator；与*this、other并发操作时行为未定义；返回*this的引用。

基类实现（L354-L365）：

concurrent_unordered_base& operator=( const concurrent_unordered_base& other ) { if (this != &other) { clear(); my_size.store(other.my_size.load(std::memory_order_relaxed), std::memory_order_relaxed); my_bucket_count.store(other.my_bucket_count.load(std::memory_order_relaxed), std::memory_order_relaxed); my_max_load_factor = other.my_max_load_factor; my_hash_compare = other.my_hash_compare; my_segments = other.my_segments; internal_copy(other); } return *this; }

注意其先clear()再逐字段快照再internal_copy的次序：先腾空自身，再从other完整重建链表与段表，因此*this原有的桶布局被整体替换为other的布局。

移动赋值

concurrent_unordered_multiset& operator=( concurrent_unordered_multiset&& other ) noexcept(/*See below*/);

以移动语义替换全部元素，other留在有效但未指定状态；当propagate_on_container_move_assignment::value为 true 时移动赋值 allocator；并发操作时行为未定义；返回*this。

noexcept 规格（规范原文）：

noexcept(std::allocator_traits<allocator_type>::is_always_equal::value && std::is_nothrow_move_assignable<hasher>::value && std::is_nothrow_move_assignable<key_equal>::value)

源码中的对应物是段表类型上的静态常量（L805-L810），移动赋值的 noexcept 参数即取unordered_segment_table::is_noexcept_assignment：

static constexpr bool is_noexcept_assignment = std::is_nothrow_move_assignable<hasher>::value && std::is_nothrow_move_assignable<key_equal>::value && segment_allocator_traits::is_always_equal::value;

两者在 allocator 语义上一致（分配器恒等 + hasher/key_equal 可无抛出移动赋值），差别仅在 is_always_equal 具体取自哪个 rebind 后的分配器 traits——对tbb_allocator与std::allocator这类无状态分配器结论相同。赋值本体（L367-L381）先clear()，再搬走 size/桶数/负载因子/哈希比较器/段表，最后按disjunction<propagate_on_container_move_assignment, is_always_equal>选择move_content（O(1) 换头）或internal_move（逐节点移动构造，L1395-L1408）。

初始化列表赋值

concurrent_unordered_multiset& operator=( std::initializer_list<value_type> init );

以init的元素替换*this的全部元素；与*this并发操作时行为未定义；返回*this。

该成员在 multiset 类体中显式重写并转发基类（concurrent_unordered_set.h#L221-L224），基类实现是最直白的两步（L383-L387）：

concurrent_unordered_base& operator=( std::initializer_list<value_type> init ) { clear(); insert(init); return *this; }

八、并发安全边界与"unsafe"约定

规范在拷贝构造、移动构造、析构和三个赋值运算符上反复标注"与容器并发操作时行为未定义"。这不是措辞上的谨慎，而是有实现的对应：基类中所有需要"稳定视图"的遍历（internal_copy、internal_move、move_content、internal_clear）都不带 CAS 保护，直接沿next()指针走。删除/摘取 API 在规范中被归入 unsafe_modifiers 与 safe_modifiers 两章，基类里也命名呼应：unsafe_erase/unsafe_extract（L496-L547）内部用__TBB_ASSERT校验"摘除操作在单线程前提下前后指针关系稳定"（unlink_node，L1249-L1256）。

由此可得实践边界：

• 并发安全：默认/指定桶数/迭代器/初始化列表构造（构造过程只做插入，插入路径本身无锁）、析构（单线程销毁整个容器是常规用法）、以及"对无其他线程接触的容器"做拷贝/移动/赋值；
• 未定义行为：在operator=、拷贝/移动构造、clear/析构进行中，另一线程并发修改同一对象；
• 若需在容器被并发读写期间获取"快照"，应改用迭代 + 插入到新建容器的自行复制策略——这与insert的并发安全性质一致。

九、验证路径：规范与实现如何对账

TBB 子树自带两层次的测试可以佐证本文所述语义：

• test/conformance/conformance_concurrent_unordered_set.cpp：标准符合性测试，按 STL 容器模型逐项校验构造、赋值、观察器等行为，是规范文档与实现之间最直接的桥梁；
• test/tbb/test_concurrent_unordered_set.cpp：功能/压力测试，覆盖插入查找、桶接口、拷贝移动等路径。

规范文档目录 concurrent_unordered_multiset_cls 下的兄弟章节（bucket 接口、查找、观察器、hash 策略、swap、并行迭代等）与本文构成完整 API 面，需要时可以顺藤摸瓜。

十、实践要点小结

1. 默认桶数并非"任意"：规范写 unspecified，vendored 实现为 8（initial_bucket_count），且任何bucket_count参数都会经round_up_to_power_of_two上取整到 2 的幂，最大负载因子初始为 4.0——预知规模时传偏大的bucket_count可减少运行期 CAS 翻倍。
2. 桶是惰性的：构造只建立段表骨架，桶虚节点随插入按需创建，空构造 + 大桶数几乎零成本；但bucket_count增大后桶数只能增不能减（rehash仅在目标更大时生效，L670-L676）。
3. 移动是最廉价的转移方式：无状态分配器下移动构造/移动赋值是 O(1) 的头指针交接，源对象回到"有效但未指定"的初始桶状态；只有 allocator 不恒等时才退化为逐节点搬移。
4. 拷贝是忠实重建：order key 与段表一并复制，无需重新散列，因此拷贝构造/赋值保留桶布局，但要求操作期间无并发修改。
5. 异常安全靠 clear 兜底：拷贝构造与带分配器的移动构造都用try_call().on_exception([&]{ clear(); })包裹逐节点复制，中途失败不会泄漏节点。
6. C++17 下可用 CTAD：迭代器/初始化列表构造有显式推导指南，Hash/KeyEqual参数不得满足 Allocator 要求，否则参与决议会被enable_if剔除。

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