Menu
The unordered associative containers unordered_set, unordered_map etc do not have a less than operator operator<, neither as a member function nor as a free function. Why? There is no specialization of less either. SGI STL's hash_* types also lack this feature.
If we exclude the concept of underlying types, all container types fulfil the requirements of regular types as defined e.g. in Stepanov & McJones' Elements of Programming. The sole exception are the unordered associative types, which lack operator<.
I could not come up with an efficient implementation of such an operator that is consistent with the given definition of equality, so might efficiency be the reason? On the other hand, operator== for unordered associative containers in some cases needs to rehash every element of one container and look it up in the other - O(N) average, but worst case O(N²).
814
7 Answers. Show activity on this post. 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.
The four unordered associative containers are called unordered_set , unordered_multiset , unordered_map , and unordered_multimap .
The comparison between unordered_map objects is not affected by the arbitrary order in which they store their elements. Two unordered_maps are equal if they have the same number of elements and the elements in one container are a permutation of the elements in the other container. Otherwise, they are unequal.
How many Associative Containers are provided by C++? Explanation: C++ provides 4 types of Associative Containers namely Set, Map, multiset and multimap.
Conceptually it doesn't make a lot of sense. Consider a bag of different colored marbles. And lets say you have two bags of marbles:
Is bag 1 < bag 2?
Even if you associate an order to the colors, say:
red < yellow < purple < blue < green
It is still difficult to say if one bag is less than than the other because internally the bag associates no order to the marbles. That is bag 1 could be output in any of 6 formats, which are all equivalent:
None of the above six are less than any of the other. Indeed, they are all equal, no matter whether red < blue or blue < red. A bag is not a sequence ... it is an unordered sequence.
Historically the unordered containers also did not have equality operators. However it does make sense to ask if one bag contains the same colored marbles as another bag. And here the issue is one of efficiency. Eventually algorithms and proposals were presented to sway the committee to add equality comparisons for the unordered containers:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
86
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
