CODEWITHSUNDEEP
c++performanceset
Fabian
Fabian

Reputation: 4211

Should I use std::set or std::unordered_set for a set of pointers?

I have a set of pointers. In the first step, I insert data pointers, and in the second step, I iterate over the whole set and do something with the elements. The order is not important, I just need to avoid duplicates, which works fine with pointer comparison.

My question is, whether it might be advantageous to use an unordered set for the same purpose. Is insertion faster for an unordered set?

Upvotes: 13

Views: 4782

Answers (1)

Yam Marcovic
Yam Marcovic

Reputation: 8141

As Ami Tavory commented, if you don't need order, then it's usually best to go for unordered containers. The reason being that if order somehow improved performance, unordered containers would still be free to use it, and hence get the same or better complexity anyhow.

A downside of unordered collections is that they usually require a hash function for the key type. If it's too hard or expensive to make one, then containers which don't use hashes might be better.

In C++'s standard library, the average insertion complexity for std::set is O(log(N)), whereas for std::unordered_set it's O(1). Aside from that, there are probably less cache misses on average when using std::unordered_set.

At the end of the day though, this is just theory. You should try something that sounds good enough and profile it to see if it really is.

Upvotes: 10

Related Questions