7

我需要检查 a 是否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是对数的，对吗？

4

2 回答 2

8

可以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)

对数时间是您可以实现的最佳时间，因为集合已排序，您需要在排序范围内找到一个元素，这需要二分搜索。

于 2012-01-25T02:53:20.117 回答
1

如果您确定要使用 a std::set，那么我同意它的lower_bound方法是要走的路。正如您所说，它将具有对数时间复杂度。

但是，根据您要执行的操作，如果您使用排序std::vector和独立std::lower_bound算法 ( std::lower_bound(v.begin(), v.end(), 3))，您的程序的整体性能可能会更好。这也是对数的，但常数较低。（当然，缺点是向 a 中插入元素std::vector并保持排序通常比向 a 中插入元素要昂贵得多std::set。）

于 2012-01-25T02:54:41.457 回答