Ordered and unordered STL containers [closed]
What are differences between ordered and unordered STL containers?
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.
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.
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 Container1 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.
1 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...
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.
First off: I assume you are talking about std::(map|set) vs the 0x std::unordered_(map|set) Well, the obvious thing first: ordered containers keep their content - well, ordered. This means extra work is needed when you insert something (because you have to find out where to insert first). However, you only need to specify (if it's not builtin, like it is for many builtin types) how to compare two elements (i.e. if one is less than the other). Unordered containers don't need to order their contents, insertion and element access is faster, but you need (for custom types) to provide a good hash function and a function testing for equality, so it's more effort on your side.
One more thing somehow overlooked in the other replies. Ordered containers require strict weak ordering either using operator<, or Traits class with operator(). As a result iterating those containers is ordered in accordance with those functions. Unordered containers only require equality comparison operator of Predicate function doing the same. Therefore, there is no ordering of elements in container (other than internal ordering of buckets).
In addition to other answers, equality test of 2 unordered containers(not elements)is difficult owing to its unordered nature. It is possible, but may be expensive.
加载中,请稍侯......
精彩评论