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 than unordered_set to store the same number of elements.
  • 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).
  • That set sorts the elements is useful if you want to access them in order.
  • You can lexicographically compare different sets with <, <=, > and >=. unordered_sets 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.