STL Set：以最高效的方式插入两百万个有序数

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/< /a>

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将是一个不错的选择。

Answer 3

如果您从全部候选 int 开始，我根本不会使用 set，我会使用 vector >，将它们全部初始化为 false，并将目标（质数）标记为 true，因为它们所在的位置。

vector<bool> candidates(200000);

您可以使用当前候选 int - 1（候选范围 = 1..200000）对此进行索引。然后使用 find 进行迭代来定位真实值，并使用偏移量与 begin() 转换为 int。

• 内存分配总数 - 1.
• 总内存使用量 25000 字节（vector 是一种特殊情况，请参阅 @Greg Rogers 的评论）与 set 的 >= 800000 ，折扣 BTree 开销。
• 所有元素访问都是通过指针算术进行的。

Answer 4

以下是一些：

1. 实现一个自定义的 stl 分配器，用于预先保留内存。

2. 如果您使用矢量解决方案，请致电保留。

3. 如果您只是要实现筛子，请使用（或实现）增强计数迭代器并且仅将结果存储在向量中，该向量调用reserve。