Menu
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?
738
For a small number of elements, lookups in a set might be faster than lookups in an unordered_set . Even though many operations are faster in the average case for unordered_set , they are often guaranteed to have better worst case complexities for set (for example insert ).
Use unordered_set whenWe need to keep a set of distinct elements and no ordering is required. We need single element access i.e. no traversal.
Set is an ordered sequence of unique keys whereas unordered_set is a set in which key can be stored in any order, so unordered. Set is implemented as a balanced tree structure that is why it is possible to maintain order between the elements (by specific tree traversal).
Even though unordered set is faster in the average case, set is almost always guaranteed to have lower worst-case complexities (for example insert). If you want to access the elements in order, that set sorts them. Different sets can be lexicographically compared using <,<=, >, and >=.
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.
114
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
