Why would anyone use set instead of unordered_set?


Question

C++0x is introducing unordered_set which is available in boost and many other places. What I understand is that unordered_set is hash table with O(1) lookup complexity. On the other hand, set is nothing but a tree with log(n) lookup complexity. Why on earth would anyone use set instead of unordered_set? i.e is there a need for set anymore?

1
128
7/30/2017 1:57:02 AM

Accepted Answer

When, for someone who wants to iterate over the items of the set, the order matters.

205
8/28/2009 10:45:12 PM

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.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon