1

Does the same code using std::unordered_set (or std::unordered_map) run on two different machines and compiled with the same exact g++ version give the same iteration order?

Related but slightly different question

I'm adding a few comments here to better explain what I'm trying to understand.

Is it enough to fix the compiler version in order to get the same behavior, in this case in terms of iteration order? Or does it depend on some other things?

Thank you for pointing out that the standard does not impose any behavior. However, the implementation must be clearly defined. In the end, it is computer code and thus it is deterministic and well-defined. The only alternative that comes to my mind is that some crazy implementation might use some real source of randomization, but I think it is very unlikely.

acco93
  • 128
  • 2
  • 11
  • `unordered` is the same, whether it's set or map. – artm Aug 03 '20 at 10:36
  • I'm sorry to have to ask this, but: Why do you ask? That is, why do you (think you) need to know the order of iteration over an unordered set? It's called "unordered" for a reason, after all... Also, tomorrow somebody changes the version of GCC. Or switches to clang++. Or the phase of the moon changes. What if the answer to your question changes? – einpoklum Aug 03 '20 at 11:27
  • @einpoklum thank you for your point. I know the containers are unordered by definition. However, the question is not about the standard but more about the implementation. In particular, I'm interested in understanding whether fixed a set of tools (in this case a given version of g++) the implementation of those structures depends on something else other than the g++ version. Does it depend on the platform/architecture? Do they use some randomization? Otherwise I cannot see how the iteration order can be different. – acco93 Aug 03 '20 at 11:58
  • 3
    It's not crazy at all to use a bit of randomization in hash maps. For example, in Go the map is randomized so as to defeat DoS attacks based on key collisions. It's not impossible to imagine some future stdlibc++ version implementing a similar randomization (though that could break quite a bit of existing code, especially in unit tests, and so is unlikely to happen). Note also that G++ and stdlibc++ are different things; you need to check mostly stdlibc++ version to ensure any kind of compatibility. – rustyx Aug 03 '20 at 13:01
  • thank you @rustyx this is probably what I was looking for. Also I imagine that even Go uses some reproducible kind of randomization (some pseudorandom engine) and not a real source of randomization. – acco93 Aug 03 '20 at 13:15
  • @acco93: But _why_ do you want to know this, rather than remain agnostic? – einpoklum Aug 03 '20 at 13:44
  • @einpoklum I have some optimization code whose final result is heavily affected by the order in which those structures are iterated. However I need to ensure some sort of reproducibility. Even if that implies selecting a given compiler and stdlib version. I know using an unordered structure was a very unfortunate design choice but it cannot be changed anymore. I was thus somehow trying to understand how to achieve that reproducibility, i.e. how many components affect this behavior. – acco93 Aug 03 '20 at 14:04
  • 1. "optimized code" and `std::unordered_map` [don't go together](https://stackoverflow.com/questions/42588264/why-is-stdunordered-map-slow-and-can-i-use-it-more-effectively-to-alleviate-t). 2. Your code should really not be affected the order of iteration... it's weird that you got that to happen :-( – einpoklum Aug 03 '20 at 16:12
  • sorry @einpoklum I'm not talking about optimized code but optimization code. That is some code to solve an optimization problem. However this is not really relevant. – acco93 Aug 03 '20 at 16:18
  • @einpoklum In such contexts doing a thing before another one may completely change the evolution of the algorithm (aka search trajectory). – acco93 Aug 03 '20 at 16:26

1 Answers1

2

There's nothing in the C++ standard to suggest it ought to.

g++ doesn't appear to have any documentation specifying above and beyond what the standard requires on this particular topic.

I'd say no then, in full generality.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483