oneTBB concurrent_multiset 非成员二元比较运算符：operator== 与 operator!= 的语义、实现与使用详解-开发者社区

并发编程
高性能计算

【免费下载链接】oneTBB

oneAPI Threading Building Blocks (oneTBB)

项目地址：https://gitcode.com/gh_mirrors/on/oneTBB

oneapi::tbb::concurrent_multiset是 oneAPI Threading Building Blocks（oneTBB）提供的有序并发容器，支持并发插入、查找与遍历。本文聚焦其"非成员二元比较"接口——operator==与operator!=，结合 oneTBB 仓库中的类定义、底层跳表实现与测试代码，完整说明两个concurrent_multiset对象之间的相等性判定规则、源码实现原理与实战用法，帮助你在并发场景中正确使用容器比较。

concurrent_multiset 与二元比较概述

在 oneTBB 中，oneapi::tbb::concurrent_multiset是一个表示有序元素序列的类模板（见 concurrent_multiset 类文档）。它具备以下核心特性：

支持并发插入（insert / emplace）、并发查找（find / count / contains）与并发遍历；
不支持并发擦除，擦除操作以unsafe_erase、unsafe_extract命名，明确标注为"concurrently unsafe"；
与concurrent_set不同，它允许多个等价元素同时存在（AllowMultimapping特性为true）；
底层基于跳表（skip list）实现，其模板参数与类定义见 include/oneapi/tbb/concurrent_set.h。

类模板的完整声明形式为：

// Defined in header <oneapi/tbb/concurrent_set.h> namespace oneapi { namespace tbb { template <typename T, typename Compare = std::less<T>, typename Allocator = tbb_allocator<T>> class concurrent_multiset { /* ... */ }; } }

其中：

模板参数	含义	默认值
`T`	元素（键）类型，`key_type`与`value_type`均为`T`	无（必填）
`Compare`	排序比较器，须满足 ISO C++ 标准 [alg.sorting] 一节对`Compare`的要求	`std::less<T>`
`Allocator`	分配器，须满足 [allocator.requirements] 一节的要求	`tbb::tbb_allocator<T>`

在类文档的 Non-member functions 一节中，oneTBB 为concurrent_multiset定义了三种非成员操作：swap、二元比较（==与!=）以及词法比较（<、<=、>、>=）。本文讨论的二元比较负责回答"两个容器是否相同"这一基本问题，而词法比较则负责回答"两个容器的元素序列谁先谁后"。

operator== 与 operator!= 的签名与语义

非成员二元比较文档给出了两个运算符的完整定义：

template <typename T, typename Compare, typename Allocator> bool operator==( const concurrent_multiset<T, Compare, Allocator>& lhs, const concurrent_multiset<T, Compare, Allocator>& rhs ) template <typename T, typename Compare, typename Allocator> bool operator!=( const concurrent_multiset<T, Compare, Allocator>& lhs, const concurrent_multiset<T, Compare, Allocator>& rhs )

operator== 的相等判定规则

根据文档，两个concurrent_multiset对象相等当且仅当同时满足两个条件：

元素个数相同（same number of elements）；
按位置逐元素相等：lhs中的每个元素都与rhs在同一位置上的元素相等。

operator==返回true当lhs等于rhs，否则返回false。

需要注意一个关键细节：这里的"元素相等"使用的是元素自身的operator==，而不是模板参数Compare所定义的排序等价关系。也就是说，相等性判定与容器内部使用的比较器无关——即便两个容器使用了不同的Compare类型（只要T与Allocator相同），只要元素序列内容相同，比较结果仍然成立。这与标准库std::multiset的比较语义一致。

operator!= 的语义

operator!=返回true当lhs不等于rhs，否则返回false。在 C++20 之前的标准 C++ 中，!=并未默认由==推导，因此 oneTBB 显式提供了该运算符；从底层源码（见下文）可以看到，其实现即为==结果的逻辑取反。

底层实现原理：从声明到跳表实现

二元比较运算符虽然以非成员函数的形式出现在文档中，但其实现并非凭空而来，而是由concurrent_multiset的基类concurrent_skip_list提供。从 include/oneapi/tbb/concurrent_set.h 可以看到：

template <typename Key, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<Key>> class concurrent_multiset : public concurrent_skip_list<set_traits<Key, Compare, geometric_level_generator<32>, Allocator, true>> { using base_type = concurrent_skip_list<set_traits<Key, Compare, geometric_level_generator<32>, Allocator, true>>; // ... };

跳表实现位于 include/oneapi/tbb/detail/_concurrent_skip_list.h：

template <typename Traits> bool operator==( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& 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 C++14 - 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_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) { return !(lhs == rhs); } #endif

实现可以拆解为两层策略，恰好对应文档描述的判定规则：

快速拒绝（short-circuit）：先调用size()比较两个容器的元素个数。一旦个数不同，直接返回false，避免了昂贵的逐元素遍历——这是std::equal的常见前置优化；
逐元素比对：在个数相同的前提下，使用std::equal对[begin, end)区间按顺序逐对比较元素。std::equal默认使用元素的operator==，从而实现了"同一位置上的元素相等"这一语义。

从源码还可以读出两个工程细节：

MSVC 兼容分支：在_MSC_VER环境下，为避免向三参数版本的std::equal传入"未检查（unchecked）"迭代器触发编译器警告，改用自 C++14 起可用的四参数重载std::equal(first1, last1, first2, last2)；
C++20 特性开关：operator!=仅在不具备 C++20 比较功能的编译环境下（!__TBB_CPP20_COMPARISONS_PRESENT）显式定义。在支持 C++20 的编译环境中，!=可由==自动推导，无需重复定义。

与词法比较的分工

值得注意的是，==/!=的底层实现只使用std::equal做逐元素相等比对，不使用Compare比较器、也不进行任何顺序比较。而排序关系则由另一组运算符负责：在同一实现文件的第 1300-1317 行，<通过std::lexicographical_compare实现，>、<=、>=分别由<推导而来：

template <typename Traits> bool operator<( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) { return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); } template <typename Traits> bool operator>( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) { return rhs < lhs; } template <typename Traits> bool operator<=( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) { return !(rhs < lhs); } template <typename Traits> bool operator>=( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) { return !(lhs < rhs); }

而在支持 C++20 概念（concepts）的编译环境下，词法比较进一步升级为直接基于std::lexicographical_compare_three_way的operator<=>（见同一文件的第 1290-1297 行），<、>等四个运算符可由其自动合成。这两组运算符（二元比较 + 词法比较）的完整文档说明分别见 non_member_binary_comparisons.rst 与 non_member_lexicographical_comparisons.rst。

命名空间与 ADL：这些运算符在哪里

文档明确说明：这些非成员函数定义的确切命名空间未指定（unspecified），只要它们能用于相应的比较操作即可。例如，实现可能将类与函数定义在某个内部命名空间中，并将oneapi::tbb::concurrent_multiset定义为类型别名，使得这些非成员函数只能通过**参数依赖查找（ADL, argument-dependent lookup）**被找到。

这带来一个实际影响：在代码中比较两个concurrent_multiset对象时，无需也不应显式限定函数所在的命名空间——直接书写lhs == rhs或lhs != rhs即可，ADL 会自动找到正确重载。这与标准库容器（如std::vector）的非成员运算符使用方式完全一致。

完整使用示例

以下是一个可直接编译运行的示例，演示二元比较的典型用法：

#include <oneapi/tbb/concurrent_set.h> #include <iostream> #include <string> int main() { // 使用默认的 std::less<std::string> 比较器 oneapi::tbb::concurrent_multiset<std::string> set_a; oneapi::tbb::concurrent_multiset<std::string> set_b; set_a.insert("alpha"); set_a.insert("beta"); set_a.insert("beta"); // multiset 允许多个等价元素 set_a.insert("gamma"); set_b.insert("alpha"); set_b.insert("beta"); set_b.insert("beta"); set_b.insert("gamma"); // 元素个数相同且每个位置元素相等 -> 相等 std::cout << "set_a == set_b : " << (set_a == set_b) << "\n"; // 1 std::cout << "set_a != set_b : " << (set_a != set_b) << "\n"; // 0 set_b.insert("delta"); // 元素个数变为 5，与 set_a 不同 std::cout << "set_a == set_b : " << (set_a == set_b) << "\n"; // 0 std::cout << "set_a != set_b : " << (set_a != set_b) << "\n"; // 1 // 元素顺序影响相等性：按位置逐元素比较 oneapi::tbb::concurrent_multiset<int> lhs{1, 2, 3}; oneapi::tbb::concurrent_multiset<int> rhs{3, 2, 1}; std::cout << "lhs == rhs : " << (lhs == rhs) << "\n"; // 0（同一位置元素不同） return 0; }

示例要点：

concurrent_multiset支持从std::initializer_list构造（构造与拷贝规则见 construction_destruction_copying.rst，迭代器接口见 iterators.rst）；
由于 multiset 允许多个等价元素，{1,2,3}与{3,2,1}元素个数相同但同一位置上的元素不同（1≠3、3≠1），因此不相等——这是"按位置逐元素比较"与"集合相等"（仅看元素多重集合）的直观区别；
若需要在不关心顺序的前提下比较元素多重集合是否一致，可先对两个容器排序，或直接使用容器自身的有序遍历结果构造标准容器后再比较。

测试验证：仓库如何检验比较语义

oneTBB 仓库对容器比较操作的正确性有专门的测试基础设施。测试辅助头文件 test/common/test_comparisons.h 提供了testEqualityComparisons：

template <bool ExpectEqual, typename T> void testEqualityComparisons( const T& lhs, const T& rhs ) { REQUIRE_MESSAGE((lhs == rhs) == ExpectEqual, "Incorrect 2-way comparison result for equal operation"); REQUIRE_MESSAGE((lhs != rhs) == !ExpectEqual, "Incorrect 2-way comparison result for unequal operation"); }

它同时校验==与!=的互补关系：==为真时!=必为假，反之亦然。若编译环境支持 C++20 比较，测试还会进一步通过testEqualityAndLessComparisons（test_comparisons.h 第 74-81 行）验证<=>的结果与二元/词法比较的一致性。

在 test/common/concurrent_ordered_common.h，有序容器公共测试会构造多种c1/c2组合（空容器、相同内容、不同内容、递增/递减序列等），并以编译期模板参数ExpectEqual、ExpectLess断言每次比较的期望结果；实际测试入口见 test/tbb/test_concurrent_set.cpp，它同时覆盖concurrent_set与concurrent_multiset，并通过REQUIRE(mset.count(i) == num_threads)等断言验证多线程插入后容器内容的正确性。

使用注意事项

比较期间避免并发修改：从实现看，operator==会完整遍历两个容器。虽然容器本身支持并发插入与查找，但比较操作不是并发安全接口——在比较进行期间若有其他线程修改容器，遍历结果将不确定。从源码结构可以推断，应当仅在容器不被其他线程修改时执行比较（例如先同步，或仅在单线程阶段使用）。
元素必须支持operator==：std::equal依赖元素类型提供可用的operator==。若元素类型只定义了Compare等价关系而未定义operator==，则二元比较无法编译；此时可考虑改用具名函数逐元素判断，而不是使用容器级==。
operator!=在 C++20 下的可用性：在 C++20 编译环境下，!=由==自动推导（源码中仅在!__TBB_CPP20_COMPARISONS_PRESENT时显式定义），使用方式不变，但要注意两者的实现路径在不同标准下有差异。
与swap的配套使用：仓库还提供非成员swap(lhs, rhs)，等价于lhs.swap(rhs)（见 non_member_swap.rst 与 concurrent_set.h 第 249-254 行）。swap与比较运算符共同构成完整的容器操作集，但swap与二元比较在语义上相互独立——交换操作不会影响任何一次比较的正确性。
比较器不影响相等判定：如前所述，operator==不调用Compare。因此两个使用不同比较器（如std::less与std::greater）但元素序列相同的 multiset，比较结果仍为相等。这与标准库std::multiset的operator==语义保持一致（标准要求对元素使用==而非比较器等价关系）。