c++ - 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?

Answer 1

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.