TBB concurrent_unordered_multiset 并发不安全修饰器（clear / unsafe_erase / unsafe

TBB concurrent_unordered_multiset 并发不安全修饰器（clear / unsafe_erase / unsafe_extract / swap）规格与源码解析

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

本文基于 TBB（Intel oneAPI Threading Building Blocks，随仓库内置于 third-party/tbb 子目录）容器规格文档 unsafe_modifiers.rst 编写，系统讲解concurrent_unordered_multiset中所有"并发不安全修饰器"的语义、前置条件与返回值约定，并对照源码实现说明每个成员函数在底层链表上实际做了什么。读完后你将掌握：如何安全地在单线程窗口内批量删除或抽离节点、透明键（transparent key）重载的 SFINAE 参与条件，以及swap的noexcept判定逻辑。

为什么这些成员函数被标记为"不安全"

规格文档开篇给出整章的总前提：

All member functions in this section can only be performed serially. The behavior is undefined in case of concurrent execution of these member functions with other (either concurrently safe) methods.

即本节的每个成员函数只能串行执行：只要它与任何其他方法（无论对方是否是并发安全方法）并发运行，行为即为未定义（UB）。这一设计与 STL 容器一致——std::unordered_multiset::erase、clear、extract同样不保证线程安全。在 TBB 的语境下，该约束的实际含义是：这些操作修改了底层分桶链表与原子大小计数器，因此必须由用户自行保证调用期间没有并发访问，典型做法是先完成并行阶段、在汇聚后的单线程阶段执行批量维护。

从源码结构看，"不安全"体现在实现上完全没有加锁：例如 internal_erase 直接断言节点非空后解链并销毁节点，internal_extract也直接改写桶内链表指针，二者都不持有任何段级互斥量，这正是文档要求串行调用的根本原因。

clear()：清空容器

声明与语义（继承自文档）：

void clear();

移除容器中的全部元素。

源码中对应 concurrent_unordered_base::clear，它是一个noexcept函数，转发到internal_clear()。值得注意的一点是：clear()出现在本"不安全"章节，意味着即使并行迭代阶段刚结束，若仍有线程在做并发安全方法（如insert）访问容器，此时调用clear()同样构成未定义行为——清空操作不是原子屏障。

unsafe_erase(pos)：按迭代器删除单个元素

文档给出两个按迭代器删除的重载：

iterator unsafe_erase( const_iterator pos ); iterator unsafe_erase( iterator pos );

效果：移除pos指向的元素；
迭代器失效：所有指向被删元素的迭代器与引用失效；
返回值：指向"被删元素之后"的迭代器（即删除后接管遍历位置的迭代器，可直接用于while (it != end()) it = unsafe_erase(it);这类循环）；
前置条件（Requirements）：pos必须有效、可解引用（dereferenceable），且指向*this中的元素。

实现见 unsafe_erase 两个 pos 重载：

iterator unsafe_erase( const_iterator pos ) { return iterator(first_value_node(internal_erase(pos.get_node_ptr()))); } iterator unsafe_erase( iterator pos ) { return iterator(first_value_node(internal_erase(pos.get_node_ptr()))); }

两个重载都委托给internal_erase，并经过 first_value_node 过滤：

value_node_ptr first_value_node( node_ptr first_node ) const { while (first_node != nullptr && first_node->is_dummy()) { first_node = first_node->next(); } return static_cast<value_node_ptr>(first_node); }

这里揭示了一个实现细节：TBB 的分桶链表内部存在 dummy 占位节点，"下一个有效元素"的返回值需要在跳过 dummy 节点后才交给用户。internal_erase本身（L1157-L1163）的流程是：断言迭代器合法 → 先取出next()→ 解链并销毁节点→ 返回下一个节点。也就是说按迭代器删除是"取出后继再销毁"的顺序，这保证了返回的迭代器一定指向仍然存活的节点（或空，即end()）。

unsafe_erase(key)：按键删除，返回删除个数

size_type unsafe_erase( const key_type& key );

效果：若容器中存在与key等价的元素，则删除该元素（multiset 语义下可能有多个等价元素）；
迭代器失效：所有指向被删元素的迭代器与引用失效；
返回值：被删除元素的个数。

由于这是 multiset，同名元素可共存，erase(key)会删除所有等价元素。源码中 unsafe_erase(key) 转发到internal_erase_by_key：

template <typename K> size_type internal_erase_by_key( const K& key ) { // TODO: consider reimplementation without equal_range - it is not effective to perform lookup over a bucket // for each unsafe_erase call auto eq_range = equal_range(key); size_type erased_count = 0; for (auto it = eq_range.first; it != eq_range.second;) { it = unsafe_erase(it); ++erased_count; } return erased_count; }

实现策略是先用equal_range(key)圈定所有等价元素的半开区间，再循环调用按迭代器的unsafe_erase。源码注释中还保留了作者的 TODO：当前做法在 multiset 场景下"每次删除都要重新查找桶"并不高效。这一内部实现细节解释了为什么按 key 删除的返回值是size_type计数，而按迭代器删除返回迭代器——两者的循环驱动方式不同。

透明键（transparent key）模板重载

template <typename K> size_type unsafe_erase( const K& key );

与 key 等价的元素若存在则删除，同样会使被删元素的迭代器与引用失效，返回删除个数。该重载只有在满足全部三个条件时才参与重载决议：

限定名hasher::transparent_key_equal合法且表示一个类型（即哈希函数承诺了透明比较能力）；
std::is_convertible<K, iterator>::value为false；
std::is_convertible<K, const_iterator>::value为false。

源码用 SFINAE 落实了这三条约束，见 L515-L522：

template <typename K> typename std::enable_if<is_transparent<K>::value && !std::is_convertible<K, const_iterator>::value && !std::is_convertible<K, iterator>::value, size_type>::type unsafe_erase( const K& key ) { return internal_erase_by_key(key); }

其中is_transparent<K>对应文档第一条hasher::transparent_key_equal检测，后两个is_convertible检查则避免字符串字面量等可隐式转换为迭代器指针的类型被误匹配。实际效果是：使用std::equal_to<void>这类透明比较器的哈希策略时，可以传入与key_type不同类型但可比较的查询键（例如用std::string_view查std::string键），而无需临时构造键对象。

unsafe_erase(first, last)：按区间批量删除

iterator unsafe_erase( const_iterator first, const_iterator last );

效果：移除半开区间[first, last)内所有元素；
返回值：指向"最后一个被删元素之后"的迭代器；
前置条件：[first, last)必须是*this中的一个合法子区间（valid subrange）。

实现见 L504-L509：

iterator unsafe_erase( const_iterator first, const_iterator last ) { while(first != last) { first = unsafe_erase(first); } return iterator(first.get_node_ptr()); }

它就是一个基于单元素unsafe_erase的线性推进循环——每次删除后返回的"后继迭代器"自然成为下一轮的first。由于删除返回的迭代器已经过first_value_node过滤 dummy 节点，循环终止条件是可靠的前进过程；当first追到last时返回last所在位置。这个写法与 STLunordered_multiset::erase(first, last)的返回约定完全对齐，方便迁移已有代码。

unsafe_extract：把节点所有权移交给 node handle

抽离（extract）与擦除（erase）的本质区别是：元素不被销毁，而是被封装进node_type（node handle），可以稍后插入本容器或其他同型容器。文档提供三个重载。

按迭代器抽离

node_type unsafe_extract( iterator pos ); node_type unsafe_extract( const_iterator pos );

将pos所指元素的所有权从容器转移到 node handle；
不会调用value_type的拷贝或移动构造（零拷贝、零移动）；
所有指向被抽离元素的迭代器失效，但指向该元素的指针和引用仍然有效（因为对象本身没有被破坏）；
返回拥有该元素的 node handle；
前置条件：pos有效、可解引用且指向*this中的元素。

实现见 L524-L532：

node_type unsafe_extract( const_iterator pos ) { internal_extract(pos.get_node_ptr()); return d1::node_handle_accessor::construct<node_type>(pos.get_node_ptr()); }

关键在于内部函数 internal_extract：

// Unsafe method, which extracts the node from the list void internal_extract( value_node_ptr node_to_extract ) { const key_type& key = traits_type::get_key(node_to_extract->value()); sokey_type hash_key = sokey_type(my_hash_compare(key)); node_ptr prev_node = prepare_bucket(hash_key); for (node_ptr node = prev_node->next(); node != nullptr; prev_node = node, node = node->next()) { if (node == node_to_extract) { unlink_node(prev_node, node, node_to_extract->next()); my_size.store(my_size.load(std::memory_order_relaxed) - 1, std::memory_order_relaxed); return; } __TBB_ASSERT(node->order_key() <= node_to_extract->order_key(), "node, which is going to be extracted should be presented in the list"); } }

对照文档语义，这里可以看到三层证据：其一，它只是把节点从链表中unlink_node摘除并原子递减my_size，没有调用析构，与"指针和引用仍然有效"的承诺吻合；其二，它依据节点自身键值重新哈希定位桶再线性查找，与"必须串行"的前提一致（无锁、无 CAS）；其三，断言检查被抽离节点必须确实位于链表中，呼应了文档对pos的 Requirements。随后node_handle_accessor::construct把这枚"裸节点"包装成node_type，完成所有权转移——这解释了为什么文档强调"不执行 value_type 的拷贝/移动构造"：对象只是换了个"外壳"。

按键抽离

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

若存在与key等价的元素，则转移该元素的所有权；
不执行value_type的拷贝/移动构造；
multiset 语义要点：若存在多个等价元素，转移其中哪一个是不确定的（unspecified）；
所有指向被抽离元素的迭代器失效，指针与引用保持有效；
返回拥有该元素的 node handle；若未找到等价元素，返回空node handle（可用empty()判断）；
模板重载的参与条件与unsafe_erase的透明键重载完全相同（transparent_key_equal合法且K不可转换为iterator/const_iterator）。

实现上两个按键重载先find再复用按迭代器抽离，见 L534-L547：

node_type unsafe_extract( const key_type& key ) { iterator item = find(key); return item == end() ? node_type() : unsafe_extract(item); }

find返回桶内命中的第一个等价元素，因此"多个等价元素时抽哪一个不确定"在实现层面就是"取查找路径先命中的那个"；找不到时返回默认构造的node_type()，与文档"空 node handle"的约定一一对应。

抽离出的 node handle 可以与insert(node_type&&)配合完成"跨容器搬迁"：先unsafe_extract摘走节点，再在目标容器中insert(std::move(nh))，全程不触碰value_type的构造/析构，适合把大对象在多个容器间重新分配的场景。

swap：整体内容互换

void swap( concurrent_unordered_multiset& other ) noexcept(/*See below*/);

交换*this与other的内容；
若std::allocator_traits<allocator_type>::propagate_on_container_swap::value为true，则连分配器一起交换；
否则（不传播），如果get_allocator() != other.get_allocator()，行为未定义；
文档给出的noexcept规格为：

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

（文档原文的 noexcept 表达式在此处截断，完整表达式以源码头文件的实际标注为准。）

源码中 swap 实现：

void swap( concurrent_unordered_base& other ) noexcept(unordered_segment_table::is_noexcept_swap) { if (this != &other) { using pocs_type = typename allocator_traits_type::propagate_on_container_swap; using is_always_equal = typename allocator_traits_type::is_always_equal; internal_swap(other, tbb::detail::disjunction<pocs_type, is_always_equal>()); } }

三个实现事实可以佐证文档的语义：第一，自交换（this == &other）被短路跳过，a.swap(a)是安全的空操作；第二，internal_swap以disjunction<pocs_type, is_always_equal>作为标签分派参数——当分配器"总是相等"时，即使分配器类型不承诺propagate_on_container_swap，交换内容也是安全的，这正是文档"否则若分配器不相等则 UB"条款在实现上的兜底判定；第三，整个方法标注为noexcept(unordered_segment_table::is_noexcept_swap)，把 noexcept 与否的判定权委托给底层分段表的静态常量，而分段表能否无抛出交换，本质上取决于其内存分配器与策略对象（hasher、key_equal）是否满足 noexcept 可交换条件，与文档 noexcept 表达式所列因子一致。

swap也属于本节"只能串行执行"的范畴：虽然它不修改单个元素的数据，但它整体替换了两容器的内部结构，若与任何并发访问同时进行同样触发未定义行为。

与文档同章规格的关系与测试佐证

该 RST 文件是concurrent_unordered_multiset完整规格的一部分，同目录下还有 safe_modifiers.rst（并发安全的增改方法）、lookup.rst、iterators.rst 等章节。理解"safe/unsafe"两套修饰器的分工是正确使用该容器的前提：

safe 修饰器（如并发insert）：任何时刻都可与彼此并行调用；
unsafe 修饰器（本文主题）：必须串行执行，且不得与任何方法并发。

容器本身的类定义见 concurrent_unordered_set.h：concurrent_unordered_multiset继承自concurrent_unordered_base，其 traits 的最后一项模板参数为true（允许同键多值，即 multimapping），这正是"按 key 删除/抽离返回计数或不确定命中对象"这一 multiset 语义的类型学根源。仓库测试侧在 test/common/concurrent_associative_common.h 与 test/common/node_handling_support.h 中对unsafe_erase、unsafe_extract等接口做了通用用例覆盖，可用于对照本文语义说明。

实用要点小结

使用窗口：所有unsafe_*成员都应在无并发访问的单线程阶段调用（典型是并行构建/迭代之后的维护阶段）；与文档总述一致，任何与它们并发的调用（无论并发方法本身是否安全）都是未定义行为。
迭代器协议：unsafe_erase(pos)与unsafe_erase(first,last)返回"删除点之后"的迭代器，是标准的 STL 式删除遍历协议；返回值已经过滤内部 dummy 节点，可直接续用。
multiset 差异：按键操作面对多个等价元素时，unsafe_erase(key)删除全部等价元素并返回计数，unsafe_extract(key)只转移其中一个（具体哪个 unspecified）；抽离未命中时得到可用empty()判定的空 node handle。
零拷贝抽离：unsafe_extract不触发value_type的拷贝/移动构造，被抽离元素的指针与引用保持有效，可配合insert(node_type&&)做容器间节点搬迁。
透明键重载：template <typename K>版本仅在hasher::transparent_key_equal有效且K不可转换为iterator/const_iterator时参与重载决议（源码中由enable_if<is_transparent<K> && ...>实现），使string_view之类查询键可免构造使用。
swap 的分配器契约：内容互换始终执行；分配器是否跟随交换取决于propagate_on_container_swap，不传播时两容器分配器必须相等，否则 UB；swap的noexcept由分配器、哈希器与比较器的可交换性共同决定，实现中委托给unordered_segment_table::is_noexcept_swap静态常量。