How make std::set insertions faster?

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?

Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/243654/discussion-on-question-by-turtle-97-how-make-set-function-faster). — Machavity, Apr 06 '22 at 13:32

eerorika · Accepted Answer · 2022-04-06T09:05:34.143

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.

How make std::set insertions faster?

1 Answers1