oneapi::tbb::concurrent_map 非成员二元比较运算符operator / operator!规范与源码实现解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文依据当前仓库所携带的 TBBoneAPI Threading Building Blocks官方规范文档 non_member_binary_comparisons.rst 展开深入讲解oneapi::tbb::concurrent_map的两个非成员二元比较运算符operator与operator!的语义定义、模板签名、底层实现以及并发场景下的使用注意事项。读者读完后将能准确理解两个并发映射何时相等的精确定义掌握其与std::map比较语义的异同并能在自己的并行程序中安全、正确地使用这两个运算符。1. 背景concurrent_map 是什么oneapi::tbb::concurrent_map是 TBB 提供的一个类模板表示一个有序关联容器sorted associative container。根据 concurrent_map_cls.rst 的类模板摘要其完整模板签名为namespace oneapi { namespace tbb { template typename Key, typename T, typename Compare std::lessKey, typename Allocator tbb_allocatorstd::pairconst Key, T class concurrent_map { // ... }; } // namespace tbb } // namespace oneapi它存储唯一键unique keys并支持并发的插入、查找与遍历但不支持并发的擦除操作擦除必须通过unsafe_erase系列方法在无并发写的情况下进行。从源码结构看concurrent_map.h 中的concurrent_map直接继承自内部实现类concurrent_skip_listmap_traits...即以**并发跳表concurrent skip list**为底层数据结构——键值按Compare严格排序因此可以保证稳定的迭代顺序这也是后文同位置元素比较语义能够成立的前提。关联性说明本仓库mold将 TBB 作为第三方依赖存放于 third-party/tbb 下并在链接器的并行实现中大量使用 TBB 的并行算法与并发容器例如 src/main.cc 中的tbb::parallel_for_each、src/main.cc 中的tbb::parallel_sort以及 src/gc-sections.cc 中的tbb::concurrent_unordered_map与tbb::concurrent_vector。本文讨论的concurrent_map正是同一套 TBB 容器体系中的有序并发容器成员。2. 非成员二元比较运算符的完整定义本关联文档 non_member_binary_comparisons.rst 定义了concurrent_map的两个**非成员函数non-member functions**形式的二元比较运算符。它们是 ADL参数依赖查找友好的自由函数模板而不是成员函数这意味着它们可以在类似a b的表达式里被自动找到而无须依赖concurrent_map自身的成员运算符。2.1 operatortemplate typename Key, typename T, typename Compare, typename Allocator bool operator( const concurrent_mapKey, T, Compare, Allocator lhs, const concurrent_mapKey, T, Compare, Allocator rhs )返回语义来自规范原文若lhs等于rhs返回true否则返回false。而等于的精确含义由规范文档开篇给出是全篇的核心定义两个oneapi::tbb::concurrent_map对象相等当且仅当它们包含相同数量的元素并且一个容器中的每个元素都与另一个容器中同一位置上的元素相等。用形式化语言表述即lhs rhs ⇔ (lhs.size() rhs.size()) ∧ ∀ i ∈ [0, size) : *(lhs 按序第 i 个元素) *(rhs 按序第 i 个元素)这里的同一位置并非随机访问下标而是指按迭代顺序对齐的同一序位——由于concurrent_map是有序容器其正序迭代顺序由键的排序决定因此该定义实际上等价于两个容器包含完全相同的键值元素集合且键的排序一致。2.2 operator!template typename Key, typename T, typename Compare, typename Allocator bool operator!( const concurrent_mapKey, T, Compare, Allocator lhs, const concurrent_mapKey, T, Compare, Allocator rhs )返回语义若lhs不等于rhs返回true否则返回false。2.3 模板参数的约束四个模板参数与concurrent_map类模板本身完全一致模板参数含义默认值类模板层面Key键类型无T映射值类型mapped_type无Compare键比较器须满足 ISO C 标准 [alg.sorting] 的Compare要求std::lessKeyAllocator分配器须满足 [allocator.requirements] 的Allocator要求tbb_allocatorstd::pairconst Key, T由于lhs与rhs的模板参数必须完全一致同类型才可比较比较运算天然要求两个容器的键类型、值类型、比较器与分配器类型完全相同。3. 底层实现从规范到源码规范文档只给出接口与语义真正的实现位于 TBB 的跳表实现头文件 detail/_concurrent_skip_list.h 中。由于concurrent_map继承自concurrent_skip_listmap_traits...这两个比较运算符是直接在concurrent_skip_list层实现的模板派生类concurrent_map、concurrent_set等通过继承自动获得template typename Traits bool operator( const concurrent_skip_listTraits lhs, const concurrent_skip_listTraits rhs ) { if (lhs.size() ! rhs.size()) return false; #if _MSC_VER // Passing unchecked iterators to std::equal with 3 parameters // causes compiler warnings. // The workaround is to use overload with 4 parameters, which is // available since C14 - minimally supported version on MSVC return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); #else return std::equal(lhs.begin(), lhs.end(), rhs.begin()); #endif } #if !__TBB_CPP20_COMPARISONS_PRESENT template typename Traits bool operator!( const concurrent_skip_listTraits lhs, const concurrent_skip_listTraits rhs ) { return !(lhs rhs); } #endif这段源码可以印证规范语义的三点关键设计短路判等先比较size()若元素数量不同直接返回false避免无谓的元素级遍历序位对齐比较用std::equal依次比较两个容器按迭代顺序对齐的每一对元素——这与规范中同一位置上的元素相等的定义逐字对应operator! 由 派生operator!直接实现为!(lhs rhs)保证两者逻辑严格互补。注意该实现受__TBB_CPP20_COMPARISONS_PRESENT宏保护在支持 C20 三路比较spaceship的编译环境中TBB 会转而利用 C20 的合成运算符来推导/!见同一文件下方基于std::lexicographical_compare_three_way的operator实现从而与标准库的重写表达式规则保持一致。另外需要留意比较的是容器内存储的元素即std::pairconst Key, T因此元素的相等性最终由Key与T各自的operator决定而与模板参数Compare键比较器无关——Compare只决定元素在容器内的排序不参与相等性判定。这一点与std::map的operator行为一致。4. 与 std::map 比较语义的对比concurrent_map的相等语义与std::map高度一致两者都是有序容器都按元素个数相同 同序位元素两两相等来判定相等。但由于底层实现不同存在两个值得注意的差异底层数据结构不同std::map通常是红黑树而concurrent_map基于并发跳表concurrent_skip_list。跳表在并发环境下通过无锁或细粒度锁机制支持并发插入与查找见 concurrent_map.h 的继承关系因此concurrent_map的迭代顺序依然是确定的按键排序保证了同位置比较的稳定性。并发可见性差异TBB 规范在 size_and_capacity.rst 中明确指出size()的返回值在存在未完成的并发插入时可能与容器真实大小不一致。由于operator第一步就依赖size()做短路判断在并发写入进行中执行a b其结果可能反映的是某一瞬间的近似状态而非确定性的最终状态。这一点是使用并发容器时必须牢记的前提。5. 使用示例下面给出一个完整可编译的示例覆盖相等、不相等、元素顺序无关性三种典型场景#include oneapi/tbb/concurrent_map.h #include iostream #include string int main() { using map_t oneapi::tbb::concurrent_mapstd::string, int; map_t a; a.emplace(alpha, 1); a.emplace(beta, 2); a.emplace(gamma, 3); // 与 a 内容完全相同的映射 map_t b; b.emplace(gamma, 3); b.emplace(beta, 2); // 注意插入顺序不同 b.emplace(alpha, 1); // 与 a 元素个数相同的映射但内容不同 map_t c; c.emplace(alpha, 1); c.emplace(beta, 2); c.emplace(delta, 4); // 元素个数不同的映射 map_t d; d.emplace(alpha, 1); d.emplace(beta, 2); std::cout std::boolalpha; std::cout a b : (a b) \n; // true数量相同同位置元素相等 std::cout a ! b : (a ! b) \n; // false std::cout a c : (a c) \n; // false第 3 个元素不同 std::cout a ! d : (a ! d) \n; // true元素个数不同短路返回 // 同名键但值不同的场景 map_t e; e.emplace(alpha, 1); e.emplace(beta, 99); std::cout a e : (a e) \n; // false元素值不同 return 0; }运行结果a b : true a ! b : false a c : false a ! d : true a e : false值得强调的关键点a与b尽管插入顺序不同由于底层跳表按键排序迭代顺序一致因此判定为相等a与c元素个数相同但第三个位置元素不同gammavsdelta判定为不相等a与d元素个数不同operator在size()检查处短路无需逐元素比较a与e键集合相同但值不同元素级operator判定不相等。6. 并发安全与使用注意事项结合规范文档与 TBB 源码使用这两个比较运算符时有几点必须注意并发写期间结果可能近似size()在存在未完成并发插入时可能返回过期值见 size_and_capacity.rst进而影响operator的判定结果。若需要严格一致的比较结果应避免在比较期间存在并发写入或采用外部同步手段。比较不是原子的容器操作operator内部对两个容器分别进行size()与元素遍历整个比较过程并非一次快照两个容器在同一时刻被并发修改时结果反映的是比较执行过程中的某个交错状态。要求同类型lhs与rhs的Key、T、Compare、Allocator必须完全一致否则编译期即无法匹配该模板。元素相等性由 Key/T 的 operator 决定与Compare无关若自定义键类型请确保其operator与排序关系语义自洽。C20 环境的行为变化在启用 C20 比较与概念的编译环境中TBB 会通过operator基于std::lexicographical_compare_three_way与重写规则提供比较运算符语义保持一致但实现路径不同。7. 相关规范与源码索引本文主体规范non_member_binary_comparisons.rst词典序比较、、、non_member_lexicographical_comparisons.rst非成员swapnon_member_swap.rst容器总览与全部非成员函数声明concurrent_map_cls.rst类模板声明与继承关系concurrent_map.hoperator/operator!的跳表层实现detail/_concurrent_skip_list.hsize()的并发语义说明size_and_capacity.rstTBB 在本仓库mold 链接器中的实际应用示例src/main.cc、src/gc-sections.cc8. 小结oneapi::tbb::concurrent_map的非成员二元比较运算符operator与operator!提供了与std::map一致、直观的容器相等性判断元素个数相同且按序位置逐元素相等即判为相等。其实现依托concurrent_skip_list层模板先比较size()短路、再用std::equal按迭代顺序逐元素比对operator!则由operator取反得到。在实际并发程序中理解比较结果在并发写入期间可能是近似值这一特性是正确使用这两个运算符的关键前提。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考