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
When, for someone who wants to iterate over the items of the set, the order matters.
Unordered sets have to pay for their O(1) average access time in a few ways:
setuses less memory than
unordered_setto store the same number of elements.
setmight be faster than lookups in an
unordered_set, they are often guaranteed to have better worst case complexities for
setsorts the elements is useful if you want to access them in order.
unordered_sets are not required to support these operations.