oneapi::tbb::concurrent_multiset 查找操作完全指南count、find、contains、lower_bound、upper_bound 与 equal_range【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldoneapi::tbb::concurrent_multiset是 oneAPI Threading Building BlocksoneTBB提供的有序并发容器允许存储多个等价元素并支持并发的插入、查找与遍历。本文以 oneTBB 官方规范中 lookup.rst 为骨架逐一剖析六大查找成员函数的签名、语义、返回规则与透明查找heterogeneous lookup约束并结合仓库中 concurrent_set.h 与_concurrent_skip_list.h的跳表实现源码说明每个 API 底层是如何工作的。读完本文你将能够在多线程场景下正确、高效地使用这些查找接口并理解其在跳表结构上的查找路径。查找操作的整体并发语义lookup.rst 文档开头给出了所有查找方法的统一前提All methods in this section can be executed concurrently with each other, concurrently-safe modifiers and while traversing the container.这句话包含三层含义是整个查找 API 设计的核心约束查找与查找之间可并发多个线程可以同时调用count、find、contains、lower_bound、upper_bound、equal_range任意组合都安全查找与并发安全修改操作可并发即查找可以与 safe_modifiers.rst 中定义的insert、emplace、merge等操作同时进行查找与遍历可并发在遍历容器见 iterators.rst的同时执行查找是安全的。需要特别注意的是concurrent_multiset不支持并发的删除操作。所有擦除类操作unsafe_erase、unsafe_extract、clear都带unsafe_前缀属于 unsafe_modifiers.rst它们与查找并发执行的结果未定义。因此查找 API 的并发保证严格限定在查找 × 查找、查找 × 安全修改与查找 × 遍历这三个组合上。关于等价equivalent的判定需要回到类模板的定义。从 concurrent_multiset_cls.rst 的类摘要可见template typename T, typename Compare std::lessT, typename Allocator tbb_allocatorT class concurrent_multiset;容器使用Compare默认std::lessT判定元素顺序两个元素a与b等价当且仅当!comp(a, b) !comp(b, a)。由于concurrent_multiset允许存储多个等价元素即多重映射源码中set_traits的allow_multimapping true因此下面所有查找接口的语义都围绕等价于 key 的元素集合展开。count统计等价元素个数count 有两个重载用于返回与key等价的元素个数size_type count( const key_type key ); template typename K size_type count( const K key );第一个版本接收容器的key_type对 multiset 而言key_type value_type T第二个是透明查找重载只有当key_compare::is_transparent为有效类型时才参与重载决议详见下文透明查找一节。count 的语义非常直接返回容器中等价于key的元素数量。对于concurrent_multiset而言由于允许多个等价元素共存返回值可以大于 1这与concurrent_set不同——对唯一的concurrent_set来说count 的结果恒为 0 或 1。从源码看_concurrent_skip_list.h中的internal_count针对是否允许多重映射做了分支template typename K size_type internal_count( const K key ) const { if (allow_multimapping) { // TODO: reimplement without double traversal std::pairconst_iterator, const_iterator r equal_range(key); return std::distance(r.first, r.second); } return size_type(contains(key) ? 1 : 0); }也就是说concurrent_multiset::count的底层实现是通过equal_range求出区间后用std::distance统计区间长度。源码中注释也明确指出这里存在双重遍历先 lower_bound 再找 upper_bound的优化空间属于实现细节不影响接口语义。仓库测试 test_concurrent_set.cpp 中的test_cycles_absense正是对 multiset count 语义的回归验证4 个线程各自向同一个tbb::concurrent_multisetint mset插入相同的i随后断言mset.count(i) num_threads即 4。这印证了 count 会完整统计所有等价元素。find查找等价元素并返回迭代器find 提供四个重载分别覆盖常量/非常量容器与普通/透明查找iterator find( const key_type key ); const_iterator find( const key_type key ) const; template typename K iterator find( const K key ); template typename K const_iterator find( const K key ) const;返回规则返回指向等价于key的元素的迭代器若不存在任何等价元素返回end()。关键语义细节如果容器中存在多个与key等价的元素返回哪一个元素是未指明的unspecified。这是多重容器multiset与唯一容器set的重要差异——concurrent_set中最多一个等价元素因此结果唯一而在concurrent_multiset中调用者不应假设 find 一定返回最早插入的元素或区间内的第一个元素。从源码看internal_find会根据allow_multimapping分发template typename K node_ptr internal_find(const K key) const { return allow_multimapping ? internal_find_multi(key) : internal_find_unique(key); }对于 multiset 走的是internal_find_multi从跳表当前最高层向下逐层搜索一旦在某层找到满足found(curr, key)即node ! nullptr !my_compare(key, get_key(node))的节点就立即返回。由于是从高层开始查找找到的往往是在高层路径上最先遇到的等价节点而非严格意义上的第一个等价元素——这正是文档声明未指明返回哪一个的底层原因。contains判断是否存在等价元素bool contains( const key_type key ) const; template typename K bool contains( const K key ) const;返回规则容器中至少存在一个与key等价的元素时返回true否则返回false。contains 是 C20 之后标准关联容器也引入的便捷接口其优势在于语义清晰调用者只关心在不在而不关心个数或具体位置。在源码层面contains的实现 就是bool contains( const key_type key ) const { return find(key) ! end(); }即内部复用 find 并与end()比较没有额外的独立查找逻辑。因此它的成本与 find 相同属于跳表上的一次并发查找。lower_bound定位第一个不小于 key 的元素iterator lower_bound( const key_type key ); const_iterator lower_bound( const key_type key ) const; template typename K iterator lower_bound( const K key ); template typename K const_iterator lower_bound( const K key ) const;返回规则返回指向容器中第一个不小于not less thankey的元素的迭代器。即返回满足!(element key)的最小元素位置若所有元素都小于key则返回end()。lower_bound 的底层实现调用internal_get_bound并以容器自身的比较器my_compare作为查找比较器iterator lower_bound( const key_type key ) { return iterator(internal_get_bound(key, my_compare)); }internal_get_bound从表头节点出发从最高层向下逐层执行internal_find_position最终返回定位到的节点——这是一条标准的跳表从左向右、自上而下的下界搜索路径。upper_bound定位第一个大于 key 的元素iterator upper_bound( const key_type key ); const_iterator upper_bound( const key_type key ) const; template typename K iterator upper_bound( const K key ); template typename K const_iterator upper_bound( const K key ) const;返回规则返回指向容器中第一个大于greater thankey的元素的迭代器若不存在这样的元素返回end()。注意 lower_bound 与 upper_bound 的分界语义lower_bound 返回不小于即语义下的第一个upper_bound 返回严格大于即语义下的第一个。两者配合即可刻画与key等价的整个区间。upper_bound 与 lower_bound 的源码实现差异仅在于比较器upper_bound使用not_greater_compareiterator upper_bound( const key_type key ) { return iterator(internal_get_bound(key, not_greater_compare(my_compare))); }not_greater_compare对原始比较器做逻辑取反包装从而把找到第一个不小于 key 的元素转化为找到第一个大于 key 的元素复用同一条internal_get_bound搜索路径。equal_range一次调用获取完整等价区间std::pairiterator, iterator equal_range( const key_type key ); std::pairconst_iterator, const_iterator equal_range( const key_type key ) const; template typename K std::pairiterator, iterator equal_range( const K key ); template typename K std::pairconst_iterator, const_iterator equal_range( const K key ) const;返回规则这是 multiset 语义最丰富的接口若容器中存在至少一个与key等价的元素返回迭代器对{f, l}f指向第一个与key等价的元素l指向紧随最后一个等价元素之后的元素即 upper_bound 的位置若不存在任何等价元素返回{end(), end()}。因此[f, l)恰好是容器中等价于key的所有元素构成的连续区间可以配合std::distance(f, l)统计个数这也正是前面提到的internal_count的做法或直接遍历区间访问所有等价元素。源码中internal_equal_range的实现思路是先用lower_bound(key)取得下界lb检查lb处的节点是否命中key若命中且为唯一容器allow_multimapping false直接让第二个迭代器前进一步result.second即得区间若命中且为多重容器则从lb节点开始用not_greater_compare沿跳表高层跳跃前进直到找到第一个大于key的节点作为区间上界若未命中保持{lb, lb}语义上等价于{end(), end()}因为此时 lb 处的元素不等于 key。透明查找Heterogeneous Lookup模板重载的参与条件本文所述六个 API 中除count/find/contains/lower_bound/upper_bound/equal_range各自的key_type版本外每个方法都还有一个template typename K版本。lookup.rst 对所有这些模板重载都给出了相同的参与条件This overload only participates in overload resolution if qualified-idkey_compare::is_transparentis valid and denotes a type.这意味着只有当你使用的比较器类型中定义了is_transparent这个类型成员例如std::less、std::greater等透明函数对象时模板版本才会进入重载决议否则编译器会忽略这些重载。透明查找的价值在于避免构造临时key_type对象例如容器存的是std::string你可以直接用const char*或std::string_view作为参数调用find而无需先构造一个临时std::string参与比较从而省去一次堆分配与拷贝。示例使用透明比较器#include oneapi/tbb/concurrent_set.h #include string oneapi::tbb::concurrent_multisetstd::string, std::less names; // 直接以字符串字面量查找无需构造临时 std::string if (names.contains(mold)) { // ... } auto it names.find(mold); auto n names.count(mold);在源码层面这些模板重载全部由is_transparent特征 配合std::enable_if门控例如template typename K typename std::enable_ifis_transparentK::value, iterator::type find( const K key ) { return iterator(internal_find(key)); }当key_compare::is_transparent不存在时is_transparentK::value为假std::enable_if使该重载被 SFINAE 移除从而保证不会与key_type版本产生歧义也不会接受类型不安全的隐式转换。实现原理并发跳表上的查找路径concurrent_multiset并非基于红黑树或 B 树而是并发跳跃表concurrent skip list。这一点可以直接从 concurrent_set.h 的类定义确认template typename Key, typename Compare std::lessKey, typename Allocator tbb::tbb_allocatorKey class concurrent_multiset : public concurrent_skip_listset_traitsKey, Compare, geometric_level_generator32, Allocator, true {几个值得注意的实现要点多重映射开关set_traits的第五个模板参数AllowMultimapping true而concurrent_set为false这是两者共享同一套跳表基类、行为却不同的根本原因。allow_multimapping直接决定了find走internal_find_multi还是internal_find_unique、count是否计算区间长度、equal_range是否需要高层跳跃找上界。随机层级节点层级由geometric_level_generator32生成最大层级上限为 32保证查找的期望复杂度为 O(log n)。免锁并发跳表节点指针使用原子操作维护例如my_head_ptr.load(std::memory_order_relaxed)、my_max_height.load(std::memory_order_acquire)查找过程只读遍历因此可以与并发插入安全共存而删除操作会改变节点链接结构故被排除在并发安全操作之外这从实现层面解释了文档开头查找可与安全修改并发、但与删除不保证并发的约定。无锁查找的代价由于并发插入随时可能改变跳表结构multiset 的internal_find_multi只能在高层路径上先到先得地返回一个等价节点无法保证返回的是最小等价元素——这正是文档中 find返回哪一个元素未指明在实现层面的体现。若需要确定性语义应使用equal_range或lower_bound组合。实战建议与选型对照综合以上 API 语义与实现给出针对concurrent_multiset查找场景的实践建议需求推荐 API说明仅判断 key 是否存在contains语义最清晰内部等价于find ! end()统计等价元素个数countmultiset 场景返回 ≥0 的整数获取任意一个等价元素find不保证返回哪个等价元素获取全部等价元素equal_range返回{f, l}闭开区间可遍历或 distance范围查询区间扫描lower_boundupper_bound经典二分边界组合可用于构建自定义范围避免构造临时 key模板重载 std::less等透明比较器前提是key_compare::is_transparent有效实践要点多重等价元素的处理由于 multiset 允许重复find的结果不确定业务上依赖具体拿到哪一个时应改用equal_range返回的f第一个等价元素或遍历整个区间。并发删除的边界查找 API 的并发安全保证不覆盖unsafe_erase/unsafe_extract/clear。若程序需要在并发修改包含删除的场景下工作需要外部同步机制或改用支持并发删除的容器。测试验证仓库测试 test_concurrent_set.cpp 覆盖了 multiset 的 count 多线程语义4 线程各插 1 份count 必须为 4可作为自己编写并发查找测试的参考模板。本文涉及的规范原文与实现源码均位于当前仓库中规范文档 lookup.rst 与容器总述 concurrent_multiset_cls.rst、头文件 concurrent_set.h、核心实现 _concurrent_skip_list.h以及测试 test_concurrent_set.cpp读者可对照阅读以获取最权威的细节。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考