如何使 std::set 插入更快？

Question

我正在使用 std::set 容器来存储一些标量整数值。我注意到当我在循环中调用它时 insert 操作很慢。我怎样才能让它更快？

这里是一些有代表性的代码：


std::set<unsigned long> k;
unsigned long s = pow(2,31);
for(unsigned long i = 0; i < s; i++){
    k.insert(i);
}

std::cout << k.size() << std::endl;

这段代码需要很长时间才能执行。我如何修改此代码（and/or 更改我的算法）以使其运行更快？

Answer 1

How make set function faster?

您可以通过使用提示来加快速度，因为您知道每次插入都会到达集合的末尾：

for(unsigned long i = 0; i < s; i++){
    k.insert(k.end(), i);
}

或者，您可以使用其他数据结构使其更快，例如 std::unordered_set。

最重要的是，您可以通过不首先创建如此庞大的集合来加快速度。例如，如果您需要知道某些 unsigned long ul 是否在整数集合 [0, s) 中，那么您可以简单地使用 ul < s 而不是创建包含所有整数的集合。

如何使 std::set 插入更快？

How make std::set insertions faster?

c++

stl

set