c++ - 如何检查一个集合是否在C++中的特定范围内具有元素

Question

我需要检查 std::set包含一个范围内的一个/多个元素。例如，如果集合是 set<int> {1, 2, 4, 7, 8} ，并给出一个 int间隔 [3, 5] (包括两个端点)，我需要知道它是否在集合中有元素。在这种情况下，返回 true。但是如果区间是[5, 6] , 返回假。间隔可能是[4, 4] , 但不是 [5, 3] .

看起来我可以使用 set::lower_bound ，但我不确定这是否是正确的方法。我还想尽可能降低复杂性。我相信使用 lower_bound是对数，正确吗？

Answer 1

您可以同时使用lower_bound 和upper_bound。您测试 3 到 5 之间的元素的示例(含)可以如下编写:

bool contains_elements_in_range = s.lower_bound(3) != s.upper_bound(5);

您可以通过切换您正在使用的函数(upper_bound 或 lower_bound)使范围包含或排除两端:

s.upper_bound(2) != s.upper_bound(5); // Tests (2, 5]
s.lower_bound(3) != s.lower_bound(6); // Tests [3, 6)
s.upper_bound(2) != s.lower_bound(6); // Tests (2, 6)

对数时间是您为此所能达到的最佳时间，因为集合已排序，您需要在排序范围内找到一个元素，这需要二分法搜索。