mold 内置 oneTBB 源码解读concurrent_multimap::value_compare 比较函数对象剖析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldoneapi::tbb::concurrent_multimap::value_compare是 TBB 并发关联容器concurrent_multimap的嵌套成员类它是一个函数对象用于直接比较容器的value_type即std::pairconst Key, T对象比较方式是对其第一分量键调用键比较函数。本文以 mold 仓库内置的 oneTBB 规范文档 value_compare_cls.rst 为主体结合 concurrent_multimap_cls.rst 与 _concurrent_skip_list.h 中的真实实现完整讲解该类的声明、成员、构造与调用语义并给出可直接落地的使用示例。读完本文你将理解 value_compare 与 key_compare 的关系、它如何被value_comp()观察器对外暴露以及如何在需要对 pair 序列按键排序的算法场景中正确使用它。一、定位concurrent_multimap 的嵌套比较器在进入value_compare本身之前先明确它在容器体系中的位置。根据 concurrent_multimap_cls.rst 的说明oneapi::tbb::concurrent_multimap是一个有序关联容器sorted associative container支持并发插入、查找与遍历concurrent insertion, lookup, and traversal不支持并发删除does not support concurrent erasure与concurrent_map最大的区别是多个具有相等键的元素可以被同时存储multiple elements with equal keys can be stored。模板参数为template typename Key, typename T, typename Compare std::lessKey, typename Allocator tbb_allocatorstd::pairconst Key, T class concurrent_multimap { ... };其中Compare即key_compare决定了元素的内部排序依据。而value_compare正是容器内定义的、把这种键序应用到整个 value 对上的适配器concurrent_multimap::value_compareis a function object that is used to compareconcurrent_multimap::value_typeobjects by comparing their first components.即它通过比较两个value_type的**第一分量first component**来比较这两个元素。因为value_type定义为std::pairconst Key, T第一分量就是键Key因此value_compare本质上是一种按 pair 的键做比较的包装。二、类声明全览Class Synopsis规范文档给出的完整类声明如下namespace oneapi { namespace tbb { template typename Key, typename T, typename Compare, typename Allocator class concurrent_multimapKey, T, Compare, Allocator::value_compare { protected: key_compare comp; value_compare( key_compare c ); public: bool operator()( const value_type lhs, const value_type rhs ) const; }; // class value_compare } // namespace tbb } // namespace oneapi从这个声明可以读出三个关键设计点value_compare是concurrent_multimap的嵌套成员类nested member class需要通过外层类限定名引用它内部保存一个key_compare类型的比较对象comp作为实际比较的载体它的构造函数是protected的用户无法直接构造只能通过容器的value_comp()观察器获取实例这一点与标准库std::map::value_compare的经典设计一致。三、成员对象存储的键比较函数对象key_compare comp;comp是 value_compare 保存的键比较函数对象The key comparison function object。它从构造时传入的key_compare复制而来之后在operator()中作为真正的比较执行器。在 mold 仓库的 oneTBB 实现中map_traits结构体内定义了这一类型见 _concurrent_skip_list.hclass value_compare { public: bool operator()(const value_type lhs, const value_type rhs) const { return comp(lhs.first, rhs.first); } protected: value_compare(compare_type c) : comp(c) {} friend struct map_traits; compare_type comp; }; // class value_compare注意这里的compare_type就是模板参数KeyCompare在concurrent_map/concurrent_multimap的上下文里即Compare与规范中的key_compare一一对应。四、构造与获取方式protected 构造函数与 value_comp()规范中的构造函数签名value_compare( key_compare c );Constructs avalue_comparewith the stored key comparison function objectc.即以传入的键比较函数对象c构造value_compare并把它存入comp成员。由于构造函数是 protected外部代码无法new或直接栈上构造唯一合法途径是调用容器的观察器observer成员value_comp()。concurrent_multimap的观察器在 concurrent_multimap_cls.rst 中声明为key_compare key_comp() const; value_compare value_comp() const;在底层跳表容器 _concurrent_skip_list.h 中这两个观察器的实现是key_compare key_comp() const { return my_compare; } value_compare value_comp() const { return container_traits::value_comp(my_compare); }而map_traits::value_comp是一个静态工厂static value_compare value_comp(compare_type comp) { return value_compare(comp); }这里的巧妙之处在于map_traits是value_compare的friendfriend struct map_traits;因此容器侧可以通过map_traits::value_comp访问 protected 构造函数而普通用户代码则完全不可见该构造函数。于是容器内部可以构造、用户只能通过value_comp()间接获得这一访问控制闭环得以成立——用户拿到的value_compare总是与容器自身的my_compare保持一致。对于concurrent_multimap而言其类型别名定义在 concurrent_map.htemplate typename Key, typename Value, typename Compare std::lessKey, typename Allocator tbb::tbb_allocatorstd::pairconst Key, Value class concurrent_multimap : public concurrent_skip_listmap_traitsKey, Value, Compare, geometric_level_generator32, Allocator, true { ... using key_compare Compare; using value_compare typename base_type::value_compare; ... };可以看到concurrent_multimap与concurrent_map共享同一套map_traits骨架区别仅在于AllowMultimapping模板参数分别传true/false。因此它们的value_compare语义完全一致本文所述内容对concurrent_map同样适用。搜索结果显示 concurrent_set.h 中也引用了value_compare可推断同族容器共享了这套比较器设计。五、调用语义operator() 的源码级解读bool operator()( const value_type lhs, const value_type rhs ) const;规范文档的原始描述是Compareslhs.firstandrhs.firstby calling the stored key comparison functioncomp.Returns:trueif first components oflhsandrhsare equal;false, otherwise.对照源码实现return comp(lhs.first, rhs.first);有两个要点需要澄清核心语义operator()对lhs与rhs的**第一分量即键**调用存储的键比较函数comp。由于Compare模板参数默认是std::lessKey且必须满足 ISO C [alg.sorting] 的Compare要求strict weak ordering严格弱序因此operator()实际上返回的是lhs.first是否先于rhs.first的序关系判断而不是两个键是否相等关于文档 Return 措辞规范文档Returns一节写的是当第一分量相等时返回 true这一文字表述与源码行为存在出入源码返回的是comp(lhs.first, rhs.first)的严格弱序结果。在 mold 仓库的这份 oneTBB 版本中实际语义以源码实现为准它返回键比较的结果用于建立value_type之间的全序关系从而支撑有序容器与基于范围的排序算法。从容器内部看concurrent_multimap的所有查找类操作find、equal_range、lower_bound、upper_bound等都以键为参数并直接使用my_compare见 _concurrent_skip_list.h 中internal_get_bound(key, my_compare)等一系列调用而value_compare的意义在于当你手头只有value_type键值对而不是分离的键时它可以让你复用同一套键序。六、典型使用场景与示例value_compare最常见的用途是把按键比较的能力带入以value_type为元素的泛型算法中。例如对某个由value_type组成的范围执行std::sort或对排序后的范围执行std::lower_bound/std::upper_bound/std::equal_range都可以传入map.value_comp()作为比较器从而保证与容器内部排序完全一致。下面给出一个基于concurrent_multimap的完整示例依赖 oneTBB 头文件 concurrent_map.h该头文件同时提供concurrent_map与concurrent_multimap#include oneapi/tbb/concurrent_map.h #include vector #include algorithm #include iostream int main() { // 默认 key_compare 为 std::lessstd::string oneapi::tbb::concurrent_multimapstd::string, int m; m.emplace(banana, 1); m.emplace(apple, 2); // multimap 允许相等键下面两个键重复也可共存 m.emplace(apple, 3); m.emplace(cherry, 4); // 通过 value_comp() 观察器获取比较器无法直接构造 value_compare auto cmp m.value_comp(); // 收集迭代器范围内的 value_type 做按键排序比较器保证与容器内序一致 std::vectoroneapi::tbb::concurrent_multimapstd::string, int::value_type elems(m.begin(), m.end()); std::sort(elems.begin(), elems.end(), cmp); for (const auto kv : elems) std::cout kv.first - kv.second \n; return 0; }运行结果将按键的字典序输出所有元素且键apple的两个条目都会保留——这正是concurrent_multimap允许重复键的体现apple - 2 apple - 3 banana - 1 cherry - 4几个值得注意的工程细节value_comp()返回的是按值拷贝的比较器其内部comp与容器构造时传入的key_compare相同由 _concurrent_skip_list.h 的container_traits::value_comp(my_compare)保证由于构造函数是 protected不要试图自行构造value_compare一律通过容器实例的value_comp()获取若用自定义Compare例如std::greaterKey或自定义结构体value_compare会自动继承该序无需额外适配concurrent_map的value_compare行为与concurrent_multimap完全一致同一map_traits骨架差异仅体现在容器是否允许重复键上。七、与 std::map::value_compare 的对照小结维度std::map::value_compareoneapi::tbb::concurrent_multimap::value_compare存储成员key_compare compkey_compare compprotected构造函数需要传入key_comparevalue_compare(key_compare c)protected获取方式通过map.value_comp()通过concurrent_multimap::value_comp()调用语义comp(lhs.first, rhs.first)comp(lhs.first, rhs.first)见 _concurrent_skip_list.h适用场景对pairconst Key, T范围按键排序/查找相同且可安全用于并发插入后的快照排序八、小结concurrent_multimap::value_compare虽然是一个很小的嵌套类却在容器的键序与范围算法之间架起了桥梁它持有key_compare通过operator()把键比较应用到std::pairconst Key, T上并通过 protected 构造 value_comp()观察器 friend 工厂的配合保证用户拿到的比较器永远与容器自身排序一致。本文所依据的规范位于 value_compare_cls.rst其父容器说明见 concurrent_multimap_cls.rst而最直接的实现证据在 _concurrent_skip_list.h 与 concurrent_map.h 中读者可以顺着这三处代码与文档交叉验证本文的全部结论。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考