c++ - STL 集 : insert two million ordered numbers in the most efficient manner

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));