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

有一个重载版本的 insert 方法,该方法将迭代器作为第一个参数。此迭代器用作提示,即比较将从此迭代器开始。因此,如果传递适当的迭代器作为提示,那么应该对集合执行非常有效的插入操作。见 here 详细情况。我相信你的案子, numbers.end() -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());

引用的链接表示,当使用基于迭代器的构造函数时,如果对迭代器进行排序,则得到线性的。但是,我没有看到任何关于如何显式通知构造函数它是排序迭代器的显式信息。

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

如果你是从全方位的候选人开始 int s、 我不会用 set 总之,我会用一个 vector<bool> false ,并将目标(质数)标记为 true

vector<bool> candidates(200000);

您可以使用当前候选项对此进行索引 内景 -1(候选范围=1..200000)。然后使用 find 要定位真值,请转换为 使用偏移量与 begin() .

• 内存分配的总数-1。
• 总内存使用量25000字节( 矢量<布尔> 是一个特例,请参见@Greg Rogers)vs>=800000中的注释 set<int> ,折扣B免费管理费。
• 所有的元素访问都是通过指针算法实现的。

1. 实现一个自定义的stl分配器,它预先对内存进行保留。

2. 如果使用矢量解,请调用reserve。

3. 如果你只是想实现筛子的使用(或实现) boost counting iterator 只将结果存储在一个称为reserve的向量中。