Ordered and unordered STL containers [closed]

Question

What are differences between ordered and unordered STL containers?

Answer 1

The main difference is that if you iterate through an ordered container by incrementing the iterator, you'll visit the elements of the container in the order of the keys.

That doesn't necessarily hold for unordered containers.

Answer 2

Ordered STL containers are based on a comparison. For example, std::set is typically implemented as a red-black tree. Unordered STL containers are based on hash algorithms and unordered_set is a hash table.

Unordered containers typically offer better algorithmic cost for operations like insertion, lookup and removal. However, their constant cost is quite high and hashing for custom types can be non-trivial in some cases. It's also impossible to iterate through an unordered container in a specific order.

Typically, I would use an ordered container for most uses, unless the performance of the container is identified to be a problem, because extending them for custom types is typically simpler.

Answer 3

The ordered and unordered apply to containers transitively.

What you are interested in is the Sequence, that is the order in which elements will appear when you iterate over (possibly a slice of) the container.

Sequence are more general though, so for this kind of concept I'll refer to the Martin Broadhurst's copy of the SGI STL website (the mother of the current STL) when one can find a taxonomy of the different concepts that lurk behind the STL.

To begin with, the Sequence. What's interesting in the sequence is that there is no guarantee that traversing it twice, without altering it in the meantime, will yield the elements in the same order. This is the case for example for containers that implement some form of caching by moving to the beginning the last element seen. In this case, iteration will effectively reverse the container.

An Ordered Associative Container¹ is a container for which a criterion order has been fixed, and that guarantees that whenever iterating over a slice of its elements you'll always encounter them ordered according to this criterion.

A Hashed Associative Container on the other hand is different. Instead of an ordering criterion it uses hashing. The SGI STL also precise it must use buckets, which is kind of restrictive. Here the iteration is basically unordered. You have absolutely no control on how the elements will get out, and it might indeed not be identical from one run of the program to the other if some sort of randomness is applied to rehashing.

An Unordered container, is the term they came up with for Boost and C++0x, because they did not want the name to clash with already existing implementation of hash_set and hash_map. And thus, though the not documented in the SGI STL, the Unordered kind approximates the previous Hashed kind.

What you really need to know: Ordered means the elements will come out sorted while Unordered means that no kind of order (at all) is enforced. Order comes at a cost, so make sure to only pay for it when you need it. For example, Python dict is actually unordered.

---

¹ I don't really like the term associative here. It's a bit misleading when one consider that a set is a model of this requirement, where an element is both key and value at once...

Answer 4

The unordered collections (tr1::unordered_map and tr1::unordered_set) retrieve values generally through a hash table implementation. This gives an amortized average look up of O(1).

The ordered collections (std::map and std::set) are node based. These collections retrieve values in O(log) time.