Why would anyone use set instead of unordered_set?
Unordered sets have to pay for their O(1) average access time in a few ways:
set
uses less memory thanunordered_set
to store the same number of elements.- For a small number of elements, lookups in a
set
might be faster than lookups in anunordered_set
. - Even though many operations are faster in the average case for
unordered_set
, they are often guaranteed to have better worst case complexities forset
(for exampleinsert
). - That
set
sorts the elements is useful if you want to access them in order. - You can lexicographically compare different
set
s with<
,<=
,>
and>=
.unordered_set
s are not required to support these operations.
When, for someone who wants to iterate over the items of the set, the order matters.
Whenever you prefer a tree to a hash table.
For instance, hash tables are "O(n)" at worst case. O(1) is the average case. Trees are "O(log n)" at worst.