Why would anyone use set instead of unordered_set?

c++ algorithm data-structures c++11
AraK picture AraK · Aug 29, 2009 · Viewed 69k times · Source

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

sth picture sth · Aug 29, 2009

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.

Related questions

what is the difference between set and unordered_set in C++?

Came across this good question, which is similar but not at all same since it talks about Java, which has different implementation of hash-tables, by virtue of having synchronized accessor /mutators Differences between HashMap and Hashtable? So what is the …

Read More
LRU cache design

Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows: 1) find the item as fast as we can 2) Once a …

Read More
balancing an AVL tree (C++)

I'm having the hardest time trying to figure out how to balance an AVL tree for my class. I've got it inserting with this: Node* Tree::insert(int d) { cout << "base insert\t" << d << …

Read More