STL Set:以最有效的方式插入200万个有序数字

Question

对于以下质量插入,因为输入是有序的,是否有任何(轻微)优化？

set<int> primes;
for ( int i = 2; i <= 2000000; i++ ) {
    primes.insert(i);
}
// then follows Sieve of Eratosthenes algorithm

---

新改进,速度提高一倍:

set<int> primes;
for ( int i = 2; i <= 2000000; i++ ) {
    primes.insert(primes.end(), i);
}
// then follows Sieve of Eratosthenes algorithm

Answer 1

来自http://www.cplusplus.com/reference/stl/set/set/

vector<int> numbers;
for (int i=2; i<=2000000; ++i)
    numbers.push_back(i);

set<int> primes(numbers.begin(), numbers.end());

这应该具有O(n)复杂度,其中你的O(n*log(n))复杂度.

引用的链接表示,当您使用基于迭代器的构造函数时,如果迭代器已排序,那么您将获得线性.但是,我没有看到任何关于如何显式通知构造函数它是一个已排序的迭代器的明确说明.

对于更干净的东西,我宁愿使用boost的计数迭代器.这缩短为:

set<int> primes(
    boost::counting_iterator<int>(0),
    boost::counting_iterator<int>(200000));

Answer 2

有一个insert可用的方法的重载版本，它将迭代器作为第一个参数。该迭代器用作提示，即比较将从该迭代器开始。因此，如果您传递正确的迭代器作为提示，那么您应该在集合上进行非常有效的插入操作。详细信息请参见此处。我相信对于你的情况，numbers.end() -1将是一个不错的选择。