企业官网建设流程全解析

TBB concurrent_multimap 并发安全修改操作详解：emplace、insert、节点合并与内部实现

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

导读

本文聚焦 oneTBB（oneAPI Threading Building Blocks）中concurrent_multimap容器的并发安全修改（Concurrently safe modifiers）接口族，完整讲解emplace、emplace_hint、全部insert重载、node_type节点插入以及容器间merge合并的签名、语义与约束。文章以 oneTBB 官方规范文档 safe_modifiers.rst 为主体，并结合本仓库 bundled 的 oneTBB 源码（concurrent_map.h、_concurrent_skip_list.h）逐层揭示这些接口背后的跳跃表（skip list）实现原理。读完本文，你将掌握在共享键值集合中安全、无锁地插入元素、搬运节点与合并容器的正确姿势，并能准确区分「安全修改」与「不安全修改」的并发边界。

说明：本文对应 oneTBB 官方规范中 concurrent_multimap 类文档的 “Concurrently safe modifiers” 章节。mold 链接器仓库将其中的 oneTBB 作为第三方依赖内置（见 third-party/tbb），本文所有源码引用均来自该内置副本。

一、什么是“并发安全修改”

oneTBB 将concurrent_multimap的所有修改操作严格划分为两类：

• Concurrently safe modifiers（并发安全修改）：本节描述的成员函数，可以彼此并发执行，也可以与查找方法（lookup）以及容器遍历并发执行。
• Concurrently unsafe modifiers（并发不安全修改）：只能串行执行；若与任何其他方法（包括安全方法）并发调用，行为未定义（详见 unsafe_modifiers.rst）。

也就是说，多个线程可以同时对同一个concurrent_multimap做emplace/insert/merge等操作，而无需外部加锁；这些操作内部由数据结构保证线程安全。从源码结构看，这一保证来自其底层实现：concurrent_multimap继承自concurrent_skip_list，并以geometric_level_generator<32>生成跳跃表节点层级、配合原子指针与内存序实现无锁并发访问，见 concurrent_map.h：

template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, Value>>> class concurrent_multimap : public concurrent_skip_list< map_traits<Key, Value, Compare, geometric_level_generator<32>, Allocator, true>> { using base_type = concurrent_skip_list<...>; ... };

注意模板最后一个参数为true，即map_traits的allow_multimapping为真，这正是multimap与map的分水岭：允许相同键存在多个元素。这一特性直接影响insert的返回值语义（见下文）。

二、原地构造元素：emplace 与 emplace_hint

2.1 emplace

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

在容器中原地构造（in-place）一个元素，构造参数由args完美转发。

• 返回：std::pair<iterator, bool>，其中iterator指向被插入的元素；布尔值恒为true。
• 要求：value_type必须满足 ISO C++ 标准 [container.requirements] 一节定义的EmplaceConstructible要求。

emplace是其余所有插入操作的地基：insert的多个重载在实现上最终都归结为emplace（见下文源码证据）。

2.2 emplace_hint

template <typename... Args> iterator emplace_hint( const_iterator hint, Args&&... args );

同样原地构造并插入一个元素，但额外接受一个hint迭代器作为「节点应放置位置的建议」。

• 返回：指向被插入元素的iterator。
• 要求：value_type必须满足EmplaceConstructible要求。

Hint 在 TBB 中仅是“建议”而非“承诺”。查看底层实现 _concurrent_skip_list.h：

template<typename... Args> iterator emplace_hint( const_iterator, Args&&... args ) { // Ignore hint return emplace(std::forward<Args>(args)...).first; }

可以看到，跳跃表版本直接忽略 hint 参数，转调emplace并取其.first返回。这一点与std::multimap的 hint 优化不同——在 TBB 的并发跳跃表中，位置提示没有实际优化作用，调用方不应依赖 hint 影响插入位置或性能。

三、插入值：insert 的六个重载

3.1 拷贝插入

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

将value拷贝进容器。

• 返回：std::pair<iterator, bool>，iterator指向被插入元素；布尔值恒为true（因为 multimap 允许重复键，插入永远不会因键冲突而失败）。
• 要求：value_type满足CopyInsertable。

3.2 带 hint 的拷贝插入

iterator insert( const_iterator hint, const value_type& other );

语义同上，hint作为放置位置建议，返回指向被插入元素的iterator。要求同样为CopyInsertable。

3.3 完美转发插入（P&& 重载）

template <typename P> std::pair<iterator, bool> insert( P&& value );

等价于emplace(std::forward<P>(value))。该重载仅在std::is_constructible<value_type, P&&>::value为true时参与重载决议（SFINAE 约束），从而避免与const value_type&重载产生歧义。从源码看，concurrent_map.h 中正是这样实现的：

template <typename P> typename std::enable_if<std::is_constructible<value_type, P&&>::value, std::pair<iterator, bool>>::type insert( P&& value ) { return this->emplace(std::forward<P>(value)); }

3.4 带 hint 的完美转发插入

template <typename P> iterator insert( const_iterator hint, P&& value );

等价于emplace_hint(hint, std::forward<P>(value))；同样仅在std::is_constructible<value_type, P&&>::value为真时参与重载决议。对应实现见 concurrent_map.h。

3.5 移动插入

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

使用移动语义插入value。

• 插入后，value处于有效但未指定（valid but unspecified）的状态，调用方不应再依赖其具体内容。
• 返回：std::pair<iterator, bool>，布尔值恒为true。
• 要求：value_type满足MoveInsertable。

3.6 带 hint 的移动插入

iterator insert( const_iterator hint, value_type&& other );

移动插入并接受位置建议；value同样被置为有效但未指定的状态。返回指向被插入元素的iterator，要求MoveInsertable。

四、插入元素序列

4.1 区间插入

template <typename InputIterator> void insert( InputIterator first, InputIterator last );

将半开区间[first, last)内的所有元素插入容器。

• 要求：InputIterator必须满足 ISO C++ 标准 [input.iterators] 一节定义的InputIterator要求。
• 注意返回值是void；如果区间内的元素由std::map/std::multimap等来源提供，其value_type应能与目标容器兼容。

4.2 初始化列表插入

void insert( std::initializer_list<value_type> init );

等价于insert(init.begin(), init.end())，即把初始化列表整体作为区间插入。

五、插入节点：node_type 与零拷贝搬运

5.1 单节点插入

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

• 若节点句柄nh为空，则什么都不做。
• 否则，将nh拥有的节点插入容器；插入成功后nh被置为空状态。
• 关键保证：插入过程中不执行value_type的任何拷贝或移动构造函数——整个节点被整体转移。
• 未定义行为：若nh非空且get_allocator() != nh.get_allocator()。
• 返回：std::pair<iterator, bool>，布尔值恒为true。

5.2 带 hint 的节点插入

iterator insert( const_iterator hint, node_type&& nh );

语义与上面相同，hint作为放置建议，nh被置空，无拷贝/移动构造；分配器不匹配时行为未定义。返回指向被插入元素的iterator。

使用场景：node_type插入通常与unsafe_extract搭配，用于把元素从另一个容器（或同一个容器）中「拔」出来再「插」进去，全程零拷贝。oneTBB 的merge内部正是这一机制的自动化版本（见下节）。

六、合并容器：merge 的四种形态

template <typename SrcCompare> void merge( concurrent_map<Key, T, SrcCompare, Allocator>& source ); template <typename SrcCompare> void merge( concurrent_map<Key, T, SrcCompare, Allocator>&& source ); template <typename SrcCompare> void merge( concurrent_multimap<Key, T, SrcCompare, Allocator>& source ); template <typename SrcCompare> void merge( concurrent_multimap<Key, T, SrcCompare, Allocator>&& source );

• 将source中的所有元素转移到*this。
• 转移过程不执行任何拷贝或移动构造。
• 若get_allocator() != source.get_allocator()，行为未定义。
• 源容器Compare可以是不同的比较器类型SrcCompare，但键类型Key、值类型T与分配器Allocator必须一致。

merge也是并发安全修改：可以与其他安全修改、查找、遍历并发执行。不过从实现看，它内部对source的遍历与摘除属于内部细节，调用方只需保证source不与自己并发操作即可（source在合并期间被修改）。

6.1 源码实现：internal_merge

merge在类中直接委托给基类的internal_merge（见 concurrent_map.h）。核心实现位于 _concurrent_skip_list.h：

template<typename SourceType> void internal_merge( SourceType&& source ) { using source_type = typename std::decay<SourceType>::type; using source_iterator = typename source_type::iterator; static_assert((std::is_same<node_type, typename source_type::node_type>::value), "Incompatible containers cannot be merged"); for (source_iterator it = source.begin(); it != source.end();) { source_iterator where = it++; if (allow_multimapping || !contains(container_traits::get_key(*where))) { node_type handle = source.unsafe_extract(where); __TBB_ASSERT(!handle.empty(), "Extracted handle in merge is empty"); if (!insert(std::move(handle)).second) { __TBB_ASSERT(!handle.empty(), "Handle should not be empty if insert fails"); // If the insertion fails - return the node into source source.insert(std::move(handle)); } __TBB_ASSERT(handle.empty(), "Node handle should be empty after the insertion"); } } }

这段代码清晰地揭示了merge的三步走机制：

1. 遍历source，对每个元素先unsafe_extract摘出node_type节点句柄；
2. 将句柄insert进目标容器（节点整体搬移，零拷贝）；
3. 若插入失败（仅concurrent_map等不允许重复键的容器会出现），则把节点归还给source。

而allow_multimapping == true时（正是concurrent_multimap的情形），条件allow_multimapping || !contains(...)恒为真，所有元素无条件转移——这与std::multimap::merge的行为一致。

七、为什么insert的 bool 恒为 true：multimap 语义

规范中反复强调：emplace与所有值型insert重载返回的std::pair<iterator, bool>，其布尔值始终为true。这与concurrent_map/std::map有本质区别：

• 在concurrent_map中，若键已存在，insert会失败，返回false；
• 在concurrent_multimap中，允许重复键，因此任何插入都会成功，bool 恒为true，iterator总是有效指向新插入的元素。

这也解释了为什么规范在 multimap 的文档里没有operator[]和at：这两个接口只对键唯一的concurrent_map有意义（见 concurrent_map.h 中at与operator[]的实现，multimap 未提供）。

八、与并发不安全修改的边界（重要提醒）

所有“安全修改”接口（本文所述的emplace、emplace_hint、全部insert、merge）可以自由并发，但以下操作被明确划为并发不安全，只能串行执行，否则行为未定义（详见 unsafe_modifiers.rst）：

• clear()：清空容器；
• unsafe_erase(pos)、unsafe_erase(key)：删除元素；
• unsafe_erase(first, last)：删除区间；
• unsafe_extract(pos)、unsafe_extract(key)：摘出节点；
• swap(other)：交换两个容器内容。

注意命名约定：TBB 刻意用unsafe_前缀标注这些操作，提醒使用者它们不具备并发安全性。而merge之所以安全，是因为其内部的摘取/插入均由concurrent_skip_list的无锁算法完成——尽管从语义上看它在“移动元素”，但它不暴露任何不安全的内部状态变更窗口。

九、实战要点小结

1. 构造 multimap：直接tbb::concurrent_multimap<K, V> m;，模板默认使用std::less<K>与tbb::tbb_allocator<std::pair<const K, V>>；也支持区间构造、初始化列表构造、拷贝/移动构造（见 construction_destruction_copying.rst）。
2. 插入首选emplace：避免临时对象的拷贝/移动，性能最好；需要位置建议时用emplace_hint，但需知晓 hint 在当前实现中会被忽略。
3. 零拷贝搬运：需要把节点从 A 容器移到 B 容器时，优先merge（整容器）或unsafe_extract+insert(node_type&&)（单节点），两者均不触发value_type的拷贝/移动构造；前提是两容器分配器相同。
4. 不要依赖 bool 判断：multimap 的插入永远成功，pair.second恒为true，不要用它做去重逻辑。
5. 删除操作串行化：clear/unsafe_erase/unsafe_extract/swap不能与任何其他方法并发；如需并发删除，请在外部加锁或用其他同步手段保护。

结语

concurrent_multimap的并发安全修改接口在设计上高度贴近 C++ 标准库std::multimap的成员函数形态，但返回值语义与并发保证完全不同：所有插入操作在跳跃表上无锁完成且永不失败，节点搬运与容器合并实现为零拷贝转移。理解这些接口的签名约束、unsafe_边界以及internal_merge的实现细节，是正确使用 TBB 并发容器、避免数据竞争与未定义行为的关键。更多接口（查找、迭代、观察器、推导指引等）可继续阅读同一目录下的 lookup.rst、iterators.rst 与 deduction_guides.rst。

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