4

In other words, if I fill two unordered_map, or unordered_set, objects with exactly the same content and the same hashing function, will iterating over them give the same sequence of key/value pairs?

If so, then what are the conditions for this to hold (e.g. same hashing function, same keys, not necessarily same values).

Gangnus
  • 24,044
  • 16
  • 90
  • 149
pms
  • 4,508
  • 4
  • 25
  • 30
  • 1
    The hash function that you're thinking of isn't actually the final hash function that gets used. The bucket size can change dynamically, and the actual hash function is *derived* from your hash function (presumably in some modular-arithmetic sort of way). – Kerrek SB Mar 24 '12 at 23:47

4 Answers4

5

No. There is no requirement, for example, that objects that have the same hash be placed in any particular order. In fact, in general it's impossible for an unordered map to do this because the only information it has access to is the hash value.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • 1
    If you add items with the same keys in the same order with the same hashing function in the same size of container (i.e. not doing anything screwy with `reserve` or whatever), what could make them be ordered differently? – Seth Carnegie Mar 24 '12 at 23:33
  • Yeah, so.. that's what I'm asking about. Even though it's not specified, in practice actually it is specified, isn't it? :) – pms Mar 24 '12 at 23:37
  • 4
    @SethCarnegie: First, the OP didn't say they'd be added in the same order. Second, anything could make them be ordered differently. The implementation could, if it wanted, order them randomly or even re-order them to put the most frequently-accessed objects first in their hash chains. – David Schwartz Mar 25 '12 at 00:21
4

The behaviour in this case is undefined. So, in some situations the sequence will be the same, in others - different. You can't be sure in anything. The types you mentioned are named unordered not by accident. Using them as ordered ones is a very very bad and extremely dangerous style.

You can find that your compiler behaves in some special way you would like to use. But you can't be sure. You mustn't be sure! You do not know, what conditions are causing such behavior of the compiler. You can never be sure that any change of the compiler version will not change the behavior you need.

What is simply forbidden in other languages, in C/C++ is not specified. But you should take it as forbidden, too.

Look c-faq about the problem of undefined behavior This concept is common for all C/C++

Gangnus
  • 24,044
  • 16
  • 90
  • 149
  • Yeah.. but from what I can read [here](http://stackoverflow.com/questions/3176621/c-is-the-unordered-map-really-unordered) it seems that it is possible... – pms Mar 24 '12 at 23:29
  • 3
    It is possible to happen so. But it is possible not to happen so. What is simply forbidden in other languages, in C/C++ is not specified. But you should take it as forbidden, too. – Gangnus Mar 24 '12 at 23:34
  • 2
    @pms: What "unordered" means is "unreliably ordered". It means that the *C++ specification* will not define an order. Your implementation of `std::unordered_*` may indeed have some consistent order. But the specification does not *enforce* this. Whereas it does enforce a specific order on `std::map`. So if you want your code to be portable, then you *cannot* rely on the ordering. – Nicol Bolas Mar 25 '12 at 01:33
2

Well first I will quote MSDN:

The actual order of elements in the controlled sequence depends on the hash function, the comparison function, the order of insertion, the maximum load factor, and the current number of buckets. You cannot in general predict the order of elements in the controlled sequence. You can always be assured, however, that any subset of elements that have equivalent ordering are adjacent in the controlled sequence.

The above quote is the same for unordered_map and unordered_set and as the name implies the sequence is unspecified, however, they do mention that equivalent keys are adjacent.

Jesse Good
  • 50,901
  • 14
  • 124
  • 166
  • 1
    I think that's only for MS's implementation isn't it? Or is it a requirement in the standard? It seems like that would force implementations to use linear probing for collisions (or store each element in an indirected dynamic array). – Seth Carnegie Mar 24 '12 at 23:47
  • 1
    @SethCarnegie: It seems its required, I found a discussion about it [here](https://groups.google.com/group/comp.std.c++/tree/browse_frm/month/2006-11/19fc7cb847e9127b?rnum=1&_done=/group/comp.std.c%2B%2B/browse_frm/month/2006-11?&hl=pt) (check post 6). – Jesse Good Mar 25 '12 at 05:49
  • We are talking about the difference between compiler-specific and undefined behaviour - terms of C/C++ ANSI standard. Any texts of MS can be very useful for their specific needs, but here work only as a comparative example. – Gangnus Jun 12 '18 at 17:05
  • The link in the 2nd comment is now a 404. As to the other comments, I don't really understand the objections here. So long as MS's implementation is compliant - which one must of course presume it is - then the allowances for variation it makes are evidence of the lack of constraints the Standard imposes. Indicating the sheer breadth of things that can affect order, without defining how they do, does not contradict the Standard eschewing a defined order. And having equivalently comparing elements adjacent is a simple fact of the bucket/chain implementation that the Standard obviously requires. – underscore_d Jan 02 '19 at 23:19
0

If you need guaranteed ordering, this is not the datastructure for you. In fact, if you're mainly going to be doing iteration, unordered_map/set is not the data structre for you, either.

For iteration, a std::map will prove to be the better data structure as gonig from one node to the next is less algorithmically complex. And the order of iteration for the objects in std::map is guaranteed by the spec (and is actually a defining property of the structure itself). (This is all assuming you're using the same comparison operator, obviously). No hashing is involved in std::map.

Suffice to say, it sounds like you're barking up the wrong tree here. unordered_map should generally be using for the benefits such as O(1) lookup and not for storing a list of objects then iterating over them. It most definitely should not be used if you're trying to get a deterministic order of iteration.

Mahmoud Al-Qudsi
  • 28,357
  • 12
  • 85
  • 125
  • Of course not. But if that's the performance-sensitive portion of your code, it may as well be the only thing you do. – Mahmoud Al-Qudsi Mar 25 '12 at 01:20
  • It's not, I use hash-tables because of a reason, and you miss the point. – pms Mar 25 '12 at 01:56
  • If you think my post missed the point, I think you're missing something. – Mahmoud Al-Qudsi Mar 25 '12 at 01:56
  • Well, I value your response and advices, but your post clearly doesn't responds to the question asked here which is "Is the order of two same unordered_maps the same?". If this is the reason why you down-voted my question then I find it aggressive, and you probably should rethink your attitude. Take care. – pms Mar 26 '12 at 16:44
  • I answered your question very plainly: order is NOT guaranteed. How hard is that to get across?!? – Mahmoud Al-Qudsi Mar 26 '12 at 20:04
  • Not really, you wrote: "If you need guaranteed ordering, this is not the datastructure for you." You used conditional here, because you assumed that I wanted guaranteed ordering, and it's not necessarily true. The only thing which matters here is the question. – pms Mar 27 '12 at 14:29