TBB concurrent_set 查找接口详解count、find、contains 与边界查找的实现解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文以 OneTBB 容器规范中concurrent_set的 Lookup查找章节为核心系统讲解count、find、contains、lower_bound、upper_bound、equal_range六个查找接口的签名、返回值语义与异构查找heterogeneous lookup规则并结合仓库内 concurrent_set.h 与 _concurrent_skip_list.h 的源码实现说明这些接口在跳表结构下的并发安全特性与底层查找路径帮助读者在多线程场景下正确使用无锁并发集合。1. Lookup 接口的总体并发保证规范原文见 lookup.rst开宗明义地给出了一条对全部查找方法都成立的并发约定All methods in this section can be executed concurrently with each other, concurrently-safe modifiers and while traversing the container.也就是说本文介绍的count、find、contains、lower_bound、upper_bound、equal_range满足三层并发安全各方法之间可以并发执行可以与并发安全修改操作concurrently-safe modifiers如insert等并发执行可以在遍历容器的同时进行。这一性质正是concurrent_set区别于std::set的关键标准库的有序容器在迭代器遍历期间不允许并发修改而 TBB 的并发集合把读读、读写并行作为规范级保证。从源码结构看concurrent_set继承自concurrent_skip_listconcurrent_set.htemplate typename Key, typename Compare std::lessKey, typename Allocator tbb::tbb_allocatorKey class concurrent_set : public concurrent_skip_listset_traitsKey, Compare, geometric_level_generator32, Allocator, false { ... };注意最后一个模板参数AllowMultimapping false——这是后文count与equal_range行为差异的根源concurrent_set键唯一concurrent_multisetAllowMultimapping true则允许重复键。所有 Lookup 接口均由基类concurrent_skip_list统一实现concurrent_set自身只暴露类型别名。2. count统计等价元素个数size_type count( const key_type key );Returns: the number of elements equivalent tokey.对于concurrent_set返回值只会是0或1对concurrent_multiset则是重复键的个数。2.1 异构查找重载template typename K size_type count( const K key );Returns: the number of elements that are equivalent tokey.该重载的参与条件参与重载决议的前提是限定名key_compare::is_transparent必须是一个合法的类型valid qualified-id。2.2 源码实现基类中的实际实现_concurrent_skip_list.hsize_type count( const key_type key ) const { return internal_count(key); } template typename K typename std::enable_ifis_transparentK::value, size_type::type count( const K key ) const { return internal_count(key); } bool contains( const key_type key ) const { return find(key) ! end(); }internal_count对两种容器走了不同分支_concurrent_skip_list.htemplate 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_set的count是一次contains即一次查找多键容器concurrent_multiset的count通过equal_range区间距离计算源码注释也坦承这是double traversal先 lower_bound 再向后扫描的临时实现。3. find定位等价元素iterator find( const key_type key ); const_iterator find( const key_type key ) const;Returns: an iterator to the element equivalent tokey, orend()if no such element exists.template typename K iterator find( const K key ); template typename K const_iterator find( const K key ) const;Returns: an iterator to the element that is equivalent tokey, orend()if no such element exists.模板重载的参与条件同样是key_compare::is_transparent合法。3.1 源码实现跳表查找路径find的实现非常薄_concurrent_skip_list.hiterator find( const key_type key ) { return iterator(internal_find(key)); }真正的核心是internal_find它按AllowMultimapping分发L828-L856template typename K node_ptr internal_find(const K key) const { return allow_multimapping ? internal_find_multi(key) : internal_find_unique(key); } template typename K node_ptr internal_find_unique( const K key ) const { const_iterator it lower_bound(key); return (it end() || my_compare(key, container_traits::get_key(*it))) ? nullptr : it.my_node_ptr; }可以看出唯一键容器的find复用lower_bound再对定位到的节点做是否严格小于 key的判断——等价即命中命中失败返回nullptr包装为end()迭代器。多键路径internal_find_multi则是一条经典跳表逐层下降搜索L833-L850for (size_type h my_max_height.load(std::memory_order_acquire); h 0; --h) { curr internal_find_position(h - 1, prev, key, my_compare); if (curr ! old_curr found(curr, key)) { return curr; } old_curr curr; }它从高到低逐层推进found的判定条件是!my_compare(key, get_key(node))节点键不小于查询键即为候选再结合逐层推进的位移检测避免空转。整个查找过程只读取my_max_heightacquire语义与节点的单向next链因此不需要加锁即可与并发插入安全并行。4. contains存在性判断bool contains( const key_type key ) const;Returns:trueif an element equivalent tokeyexists in the container;false, otherwise.template typename K bool contains( const K key ) const;模板重载同样以key_compare::is_transparent为参与条件。实现上contains直接等于查找未落空_concurrent_skip_list.hbool contains( const key_type key ) const { return find(key) ! end(); }因此在唯一键容器里contains(key) (count(key) 1)在多线程是否存在某 key的高频检查场景例如缓存命中判断、去重判断contains与find的成本相同选择哪个取决于是否需要持有迭代器。5. lower_bound 与 upper_bound边界查找5.1 lower_bounditerator lower_bound( const key_type key ); const_iterator lower_bound( const key_type key ) const;Returns: an iterator to the first element in the container that isnot lessthankey.template typename K iterator lower_bound( const K key ) template typename K const_iterator lower_bound( const K key ) const模板重载参与条件不变key_compare::is_transparent合法。5.2 upper_bounditerator upper_bound( const key_type key ); const_iterator upper_bound( const key_type key ) const;Returns: an iterator to the first element in the container that comparesgreaterthankey.template typename K iterator upper_bound( const K key ); template typename K const_iterator upper_bound( const K key ) const;两个接口与标准库std::set的语义完全对齐lower_bound找不小于的首个元素upper_bound找严格大于的首个元素二者之差即为等价元素的数量。源码中它们同样是enable_ifis_transparentK::value, ...门控的模板重载_concurrent_skip_list.h例如typename std::enable_ifis_transparentK::value, iterator::type lower_bound( const K key ) { ... }6. equal_range等价区间std::pairiterator, iterator equal_range( const key_type key ); std::pairconst_iterator, const_iterator equal_range( const key_type key ) const;Returns: if an element equivalent tokeyexists, a pair of iterators{f, l}, wherefis an iterator to this element,lisstd::next(f). Otherwise,{end(), end()}.template typename K std::pairiterator, iterator equal_range( const K key ) template typename K std::pairconst_iterator, const_iterator equal_range( const K key )注意规范对concurrent_set的措辞区间形式是{f, std::next(f)}——因为键唯一等价区间长度至多为 1对concurrent_multisetl则是第一个不等价元素的位置。6.1 源码实现的双路径internal_equal_range_concurrent_skip_list.htemplate typename K std::pairiterator, iterator internal_equal_range(const K key) const { iterator lb get_iterator(lower_bound(key)); auto result std::make_pair(lb, lb); // If the lower bound points to the node with the requested key if (found(lb.my_node_ptr, key)) { if (!allow_multimapping) { // For unique containers - move the second iterator forward and exit result.second; } else { // For multi containers - find the upper bound starting from the lower bound node_ptr prev lb.my_node_ptr; ... } } return result; }唯一键容器命中后第二个迭代器直接前移一步O(1) 完成多键容器从 lower bound 出发沿跳表高层向下做上界搜索把第一个大于 key的节点作为l。这也解释了第 2 节internal_count在多键分支中调用equal_range的原因——区间长度就是重复键个数。7. 异构查找Transparent Comparison机制规范反复出现的一句话值得专门解释This overload only participates in overload resolution if qualified-idkey_compare::is_transparentis valid and denotes a type.这是 C14 引入的异构查找transparent comparator机制当比较器定义了嵌套类型别名is_transparent时模板版本的重载才会进入重载决议。实践中常见写法是struct ci_less { using is_transparent void; // 启用异构查找的关键 bool operator()(const char* lhs, const char* rhs) const { return strcasecmp(lhs, rhs) 0; } template typename L, typename R bool operator()(const L l, const R r) const; };此时std::concurrent_setstd::string, ci_less就能直接以const char*作为查询键避免为查找构造临时std::string。在 TBB 源码中这一规则通过两层 trait 落地_concurrent_skip_list.husing is_transparent dependent_boolcomp_is_transparentkey_compare, T;comp_is_transparentkey_compare检测key_compare::is_transparent是否合法类型dependent_bool..., T再把它折算为依赖模板参数T的布尔开关。随后每个模板重载用std::enable_ifis_transparentK::value, ...作为返回类型门控——若比较器不支持透明比较模板版本对编译器不可见自然回落到const key_type重载行为与标准库一致。8. 使用示例与配合遍历的并发语义结合规范对迭代器的约束iterator/const_iterator满足ForwardIterator要求见 iterators.rst一个典型的并发读模式如下#include oneapi/tbb/concurrent_set.h #include oneapi/tbb/parallel_for.h int main() { tbb::concurrent_setint cs; for (int i 0; i 100; i) cs.insert(i * 2); // 唯一键重复键不插入 // 1) 存在性与计数 bool hit cs.contains(42); // true auto n cs.count(42); // 1 tbb::concurrent_setint::iterator it cs.find(42); // 2) 边界查找第一个 50 的键 auto lb cs.lower_bound(50); // 指向 50 auto ub cs.upper_bound(50); // 指向 52 auto [f, l] cs.equal_range(50); // {it50, it52} // 3) 遍历期间允许并发执行本文所有 Lookup 方法 tbb::parallel_for(0, 4, { for (auto it cs.begin(); it ! cs.end(); it) { volatile int v *it; // 消费元素 } }); return 0; }要点回顾find/contains/count/lower_bound/upper_bound/equal_range可两两并发也可与并发安全修改操作、遍历同时执行规范 Lookup 节首段唯一键容器的count至多返回 1equal_range的第二个迭代器是std::next(f)模板重载仅当key_compare::is_transparent合法时参与重载决议这是零临时对象异构查询的前提所有接口的实现集中在基类concurrent_skip_listinternal_find、internal_count、internal_equal_rangeconcurrent_set与concurrent_multiset的差异仅由AllowMultimapping开关驱动。9. 相关文档索引本文依据的规范章节lookup.rst容器头文件concurrent_set.hconcurrent_set与concurrent_multiset定义查找实现_concurrent_skip_list.h迭代器语义iterators.rst并发安全修改操作safe_modifiers.rst容量与观察接口observers.rst、size_and_capacity.rst【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 TBB concurrent_set 查找接口详解：count、find、contains 与边界查找的实现解析
TBB concurrent_set 查找接口详解count、find、contains 与边界查找的实现解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文以 OneTBB 容器规范中concurrent_set的 Lookup查找章节为核心系统讲解count、find、contains、lower_bound、upper_bound、equal_range六个查找接口的签名、返回值语义与异构查找heterogeneous lookup规则并结合仓库内 concurrent_set.h 与 _concurrent_skip_list.h 的源码实现说明这些接口在跳表结构下的并发安全特性与底层查找路径帮助读者在多线程场景下正确使用无锁并发集合。1. Lookup 接口的总体并发保证规范原文见 lookup.rst开宗明义地给出了一条对全部查找方法都成立的并发约定All methods in this section can be executed concurrently with each other, concurrently-safe modifiers and while traversing the container.也就是说本文介绍的count、find、contains、lower_bound、upper_bound、equal_range满足三层并发安全各方法之间可以并发执行可以与并发安全修改操作concurrently-safe modifiers如insert等并发执行可以在遍历容器的同时进行。这一性质正是concurrent_set区别于std::set的关键标准库的有序容器在迭代器遍历期间不允许并发修改而 TBB 的并发集合把读读、读写并行作为规范级保证。从源码结构看concurrent_set继承自concurrent_skip_listconcurrent_set.htemplate typename Key, typename Compare std::lessKey, typename Allocator tbb::tbb_allocatorKey class concurrent_set : public concurrent_skip_listset_traitsKey, Compare, geometric_level_generator32, Allocator, false { ... };注意最后一个模板参数AllowMultimapping false——这是后文count与equal_range行为差异的根源concurrent_set键唯一concurrent_multisetAllowMultimapping true则允许重复键。所有 Lookup 接口均由基类concurrent_skip_list统一实现concurrent_set自身只暴露类型别名。2. count统计等价元素个数size_type count( const key_type key );Returns: the number of elements equivalent tokey.对于concurrent_set返回值只会是0或1对concurrent_multiset则是重复键的个数。2.1 异构查找重载template typename K size_type count( const K key );Returns: the number of elements that are equivalent tokey.该重载的参与条件参与重载决议的前提是限定名key_compare::is_transparent必须是一个合法的类型valid qualified-id。2.2 源码实现基类中的实际实现_concurrent_skip_list.hsize_type count( const key_type key ) const { return internal_count(key); } template typename K typename std::enable_ifis_transparentK::value, size_type::type count( const K key ) const { return internal_count(key); } bool contains( const key_type key ) const { return find(key) ! end(); }internal_count对两种容器走了不同分支_concurrent_skip_list.htemplate 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_set的count是一次contains即一次查找多键容器concurrent_multiset的count通过equal_range区间距离计算源码注释也坦承这是double traversal先 lower_bound 再向后扫描的临时实现。3. find定位等价元素iterator find( const key_type key ); const_iterator find( const key_type key ) const;Returns: an iterator to the element equivalent tokey, orend()if no such element exists.template typename K iterator find( const K key ); template typename K const_iterator find( const K key ) const;Returns: an iterator to the element that is equivalent tokey, orend()if no such element exists.模板重载的参与条件同样是key_compare::is_transparent合法。3.1 源码实现跳表查找路径find的实现非常薄_concurrent_skip_list.hiterator find( const key_type key ) { return iterator(internal_find(key)); }真正的核心是internal_find它按AllowMultimapping分发L828-L856template typename K node_ptr internal_find(const K key) const { return allow_multimapping ? internal_find_multi(key) : internal_find_unique(key); } template typename K node_ptr internal_find_unique( const K key ) const { const_iterator it lower_bound(key); return (it end() || my_compare(key, container_traits::get_key(*it))) ? nullptr : it.my_node_ptr; }可以看出唯一键容器的find复用lower_bound再对定位到的节点做是否严格小于 key的判断——等价即命中命中失败返回nullptr包装为end()迭代器。多键路径internal_find_multi则是一条经典跳表逐层下降搜索L833-L850for (size_type h my_max_height.load(std::memory_order_acquire); h 0; --h) { curr internal_find_position(h - 1, prev, key, my_compare); if (curr ! old_curr found(curr, key)) { return curr; } old_curr curr; }它从高到低逐层推进found的判定条件是!my_compare(key, get_key(node))节点键不小于查询键即为候选再结合逐层推进的位移检测避免空转。整个查找过程只读取my_max_heightacquire语义与节点的单向next链因此不需要加锁即可与并发插入安全并行。4. contains存在性判断bool contains( const key_type key ) const;Returns:trueif an element equivalent tokeyexists in the container;false, otherwise.template typename K bool contains( const K key ) const;模板重载同样以key_compare::is_transparent为参与条件。实现上contains直接等于查找未落空_concurrent_skip_list.hbool contains( const key_type key ) const { return find(key) ! end(); }因此在唯一键容器里contains(key) (count(key) 1)在多线程是否存在某 key的高频检查场景例如缓存命中判断、去重判断contains与find的成本相同选择哪个取决于是否需要持有迭代器。5. lower_bound 与 upper_bound边界查找5.1 lower_bounditerator lower_bound( const key_type key ); const_iterator lower_bound( const key_type key ) const;Returns: an iterator to the first element in the container that isnot lessthankey.template typename K iterator lower_bound( const K key ) template typename K const_iterator lower_bound( const K key ) const模板重载参与条件不变key_compare::is_transparent合法。5.2 upper_bounditerator upper_bound( const key_type key ); const_iterator upper_bound( const key_type key ) const;Returns: an iterator to the first element in the container that comparesgreaterthankey.template typename K iterator upper_bound( const K key ); template typename K const_iterator upper_bound( const K key ) const;两个接口与标准库std::set的语义完全对齐lower_bound找不小于的首个元素upper_bound找严格大于的首个元素二者之差即为等价元素的数量。源码中它们同样是enable_ifis_transparentK::value, ...门控的模板重载_concurrent_skip_list.h例如typename std::enable_ifis_transparentK::value, iterator::type lower_bound( const K key ) { ... }6. equal_range等价区间std::pairiterator, iterator equal_range( const key_type key ); std::pairconst_iterator, const_iterator equal_range( const key_type key ) const;Returns: if an element equivalent tokeyexists, a pair of iterators{f, l}, wherefis an iterator to this element,lisstd::next(f). Otherwise,{end(), end()}.template typename K std::pairiterator, iterator equal_range( const K key ) template typename K std::pairconst_iterator, const_iterator equal_range( const K key )注意规范对concurrent_set的措辞区间形式是{f, std::next(f)}——因为键唯一等价区间长度至多为 1对concurrent_multisetl则是第一个不等价元素的位置。6.1 源码实现的双路径internal_equal_range_concurrent_skip_list.htemplate typename K std::pairiterator, iterator internal_equal_range(const K key) const { iterator lb get_iterator(lower_bound(key)); auto result std::make_pair(lb, lb); // If the lower bound points to the node with the requested key if (found(lb.my_node_ptr, key)) { if (!allow_multimapping) { // For unique containers - move the second iterator forward and exit result.second; } else { // For multi containers - find the upper bound starting from the lower bound node_ptr prev lb.my_node_ptr; ... } } return result; }唯一键容器命中后第二个迭代器直接前移一步O(1) 完成多键容器从 lower bound 出发沿跳表高层向下做上界搜索把第一个大于 key的节点作为l。这也解释了第 2 节internal_count在多键分支中调用equal_range的原因——区间长度就是重复键个数。7. 异构查找Transparent Comparison机制规范反复出现的一句话值得专门解释This overload only participates in overload resolution if qualified-idkey_compare::is_transparentis valid and denotes a type.这是 C14 引入的异构查找transparent comparator机制当比较器定义了嵌套类型别名is_transparent时模板版本的重载才会进入重载决议。实践中常见写法是struct ci_less { using is_transparent void; // 启用异构查找的关键 bool operator()(const char* lhs, const char* rhs) const { return strcasecmp(lhs, rhs) 0; } template typename L, typename R bool operator()(const L l, const R r) const; };此时std::concurrent_setstd::string, ci_less就能直接以const char*作为查询键避免为查找构造临时std::string。在 TBB 源码中这一规则通过两层 trait 落地_concurrent_skip_list.husing is_transparent dependent_boolcomp_is_transparentkey_compare, T;comp_is_transparentkey_compare检测key_compare::is_transparent是否合法类型dependent_bool..., T再把它折算为依赖模板参数T的布尔开关。随后每个模板重载用std::enable_ifis_transparentK::value, ...作为返回类型门控——若比较器不支持透明比较模板版本对编译器不可见自然回落到const key_type重载行为与标准库一致。8. 使用示例与配合遍历的并发语义结合规范对迭代器的约束iterator/const_iterator满足ForwardIterator要求见 iterators.rst一个典型的并发读模式如下#include oneapi/tbb/concurrent_set.h #include oneapi/tbb/parallel_for.h int main() { tbb::concurrent_setint cs; for (int i 0; i 100; i) cs.insert(i * 2); // 唯一键重复键不插入 // 1) 存在性与计数 bool hit cs.contains(42); // true auto n cs.count(42); // 1 tbb::concurrent_setint::iterator it cs.find(42); // 2) 边界查找第一个 50 的键 auto lb cs.lower_bound(50); // 指向 50 auto ub cs.upper_bound(50); // 指向 52 auto [f, l] cs.equal_range(50); // {it50, it52} // 3) 遍历期间允许并发执行本文所有 Lookup 方法 tbb::parallel_for(0, 4, { for (auto it cs.begin(); it ! cs.end(); it) { volatile int v *it; // 消费元素 } }); return 0; }要点回顾find/contains/count/lower_bound/upper_bound/equal_range可两两并发也可与并发安全修改操作、遍历同时执行规范 Lookup 节首段唯一键容器的count至多返回 1equal_range的第二个迭代器是std::next(f)模板重载仅当key_compare::is_transparent合法时参与重载决议这是零临时对象异构查询的前提所有接口的实现集中在基类concurrent_skip_listinternal_find、internal_count、internal_equal_rangeconcurrent_set与concurrent_multiset的差异仅由AllowMultimapping开关驱动。9. 相关文档索引本文依据的规范章节lookup.rst容器头文件concurrent_set.hconcurrent_set与concurrent_multiset定义查找实现_concurrent_skip_list.h迭代器语义iterators.rst并发安全修改操作safe_modifiers.rst容量与观察接口observers.rst、size_and_capacity.rst【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考