如何在C++中检查集合是否包含某个范围内的元素

Question

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

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

Answer 1

您可以一起使用lower_bound和upper_bound。您的3到5（含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)

对数时间是您可以达到的最佳时间，因为对集合进行了排序，并且您需要在排序范围内查找元素，这需要进行二分法搜索。