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

Question

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

下面是一些代表性代码：

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;

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

Answer 1

如何让 set 函数更快？

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

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

或者，您也可以使用其他数据结构（例如 std::unordered_set）来加快速度例子。

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