Why use an unordered container? (C++)

Question

I have already tried searching for this but haven't found anything.

I am learning about STL containers, and understand the pros and cons of sequential and associative containers, however am not sure why anyone would prefer an unordered container over an associative one, as surely it would not affect element insertion, lookup and removal.

Is it purely a performance thing, i.e it would take more processing to insert / remove to an associative container as it has to go through sorting? I don't know too much about the system side of things but in my head I feel like an unordered container would require more 'upkeep' than one that is automatically organised.

If anyone could shed some light it would be really appreciated.

Answer 1

Purely abstractly, consider the fact that an ordering of the elements is an extra "feature" that you have to pay for, so if you don't need it (like in lookup-only dictionary), then you shouldn't have to pay for it.

Technically this means that an unordered container can be implemented with expected lookup and in­ser­tion complexity O(1), rather than the O(log n) of ordered containers, by using hash tables.

On a tangentially related note, though, there is a massive practical advantage when using strings as keys: An ordered container has to perform full string comparison everywhere along the tree walk, while a hash container only performs a single hashing operation (which can even be "optimized" to only sam­ple a fixed number of characters from very long strings), and often turns out to be a lot faster in practice.

If ordering is not a requirement, then the best thing to do is to try out both container types (whose inter­face is almost identical) and compare the performance in your usage profile.