How make std::set insertions faster? [duplicate]

Question

I am using the std::set container to store some scalar integer values. I've noticed that the insert operation is slow when I call it in a loop. How can I make it faster?

Here is some representative code:

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;

This code takes a very long time to execute. How can I modify this code (and/or change my algorithm) in order to make it run faster?

Answer 1

How make set function faster?

You can make this faster by using hints, since you know that every insert is to the end of the set:

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

Alternatively, you could potentially make it faster using another data structure, such as std::unordered_set for example.

Most significantly, you could make it faster by not creating such a massive set in the first place. For example, if you need to know whether some unsigned long ul is in the set of integers [0, s), then you can simply use ul < s instead of creating the set that contains all the integers.