c++ - 如何有效地将一系列连续整数插入到 std::set 中？

Question

在 C++ 中，我有一个 std::set，我想插入一系列连续的整数。我怎样才能有效地做到这一点，希望在 O(n) 时间内完成，其中 n 是范围的长度？

我想我会使用 std::insert 的 inputIterator 版本，但不清楚如何构建输入迭代器。

std::set<int> mySet;

// Insert [34 - 75):
mySet.insert(inputIteratorTo34, inputIteratorTo75);

我如何创建输入迭代器，范围大小是否为 O(n)？

Answer 1

将已排序的元素插入集合的有效方法是提示库下一个元素的位置。为此，您要使用 insert 的版本需要一个迭代器:

std::set<int>::iterator it = mySet.end();
for (int x : input) {
   it = mySet.insert(it, x);
}

另一方面，您可能需要考虑其他容器。尽可能使用 std::vector .如果与查找相比插入量较小，或者如果所有插入都是预先发生的，那么您可以构建一个 vector ，对其进行排序并使用 lower_bound用于查找。在这种情况下，由于输入已经排序，您可以跳过排序。

如果到处都发生插入(或删除)，您可能需要考虑使用 std::unordered_set<int>平均 O(1)插入(每个元素)和查找成本。

对于跟踪集合中小数字的特殊情况，所有小数字(34 到 75 都是小数字)，您还可以考虑使用位集，甚至是 bool 的普通数组。在其中将元素设置为 true插入时。两者都会有 O(n)插入(所有元素)和 O(1) lookup(每次查找)，比set要好。