如何使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;

执行此代码需要很长时间。如何修改此代码(和/或更改算法(以使其运行更快？

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 < s，而不是创建包含所有整数的集