3

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

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

std::set<int> mySet;

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

如何创建输入迭代器，这将是范围大小的 O(n) 吗？

4

5 回答 5

4

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

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

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

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

对于跟踪集合中的小数字的特殊情况，所有这些数字都很小（34 到 75 是小数字），您还可以考虑使用位集，甚至是在插入时bool将元素设置为的普通数组。true无论是O(n)插入（所有元素）和O(1)查找（每个查找），都比集合好。

于 2013-08-18T03:22:11.473 回答
2

Boost方式可能是：

 std::set<int> numbers(
 boost::counting_iterator<int>(0),
 boost::counting_iterator<int>(10));

其他答案的绝佳链接，特别是@Mani的答案

于 2013-08-18T03:26:11.873 回答
1

接受aksham提供的提示，我看到答案是：

#include <boost/iterator/counting_iterator.hpp>

std::set<int> mySet;

// Insert [34 - 75):
mySet.insert(boost::counting_iterator<int>(34),
             boost::counting_iterator<int>(75));
于 2013-08-18T05:09:15.430 回答
1

std::set 是一种二叉搜索树，这意味着平均插入成本为 O(lgn)，

c++98：如果插入了 N 个元素，通常为 Nlog(size+N)，但如果元素已经根据容器使用的相同排序标准排序，则为 size+N 线性。

c++11：如果插入N个元素，Nlog(size+N)。如果范围已经排序，则实现可能会优化。

我认为 C++98 实现将跟踪当前插入节点并检查要插入的下一个值是否大于当前值，在这种情况下，无需再次从根开始。

在c++11中，这是一个可选的优化，所以你可以实现一个skiplist结构，并在你的实现中使用这个范围插入特征，或者你可以根据你的场景优化程序

于 2013-08-18T03:27:27.020 回答
0

目前尚不清楚为什么您特别想使用迭代器插入以指定范围。

但是，我相信您可以使用简单的 for 循环插入所需的 O(n) 复杂度。

引用 cppreference 在 std::set 上的页面，复杂性是：

如果插入了 N 个元素，则通常为 Nlog(size+N)，但如果元素已根据容器使用的相同排序标准排序，则为 size+N 线性。

因此，使用 for 循环：

std::set<int> mySet;
for(int i = 34; i < 75; ++i) 
  mySet.insert(i);
于 2013-08-18T03:25:50.873 回答