21xrx.com
2024-11-22 04:08:02 Friday
登录
文章检索 我的文章 写文章
C++ Map 查找范围详解
2023-07-09 04:49:04 深夜i     --     --
C++ Map 查找范围 详解

C++ Map 是一种关联容器,其中的键值对(key-value pairs)被存储成集合的形式。由于 Map 使用红黑树实现,因此查找元素的复杂度为 O(log n)。在 Map 中,键值对是按照键值升序排列的,因此我们可以使用 Map 查找范围实现各种有用的操作。

Map 查找范围是指在 Map 中查找从一个键值范围到另一个键值范围的所有键值对。Map 提供了两个函数:lower_bound 和 upper_bound 可以用于查找范围。

lower_bound

lower_bound(start, end, value) 函数可以查找 Map 中键值第一个大于等于 value 的元素,并返回它的迭代器。start 和 end 分别是 Map 中查找范围的迭代器,通常指向 begin() 和 end() 函数返回的迭代器。例如,在以下 Map 中查找键值范围为 [3, 7] 的所有键值对:

std::map my_map = {1, 2, 3,

                40, 5, 6,

                70, 8, 9};

auto start = my_map.lower_bound(3);

auto end = my_map.upper_bound(7);

for (auto it = start; it != end; ++it)

 std::cout << it->first << " " << it->second << "\n";

输出结果为:

3 30

4 40

5 50

6 60

7 70

upper_bound

upper_bound(start, end, value) 函数可以查找 Map 中键值第一个大于 value 的元素,并返回它的迭代器。如果不存在这样的元素,则返回 end 迭代器。使用方法与 lower_bound 相同:

auto it = my_map.upper_bound(3);

if (it == my_map.end())

 std::cout << "No element found\n";

else

 std::cout << it->first << " " << it->second << "\n";

输出结果为:

4 40

总结

C++ Map 查找范围提供了快速、有效地查找.Map 中某个特定键值范围内的所有键值对的方法。lower_bound 和 upper_bound 函数允许我们在 Map 中执行复杂的查找操作,并返回仅有特定键值范围内的元素。这些函数能够充分利用 Map 数据结构的效率和计算资源,帮助开发者解决复杂的算法问题。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复