Does the C++11 standard require that two iterations through a constant unordered_container visit elements in the same order?

Question

for (auto&& i : unordered_container)
{ /* ... */ }

for (auto&& i : unordered_container)
{ /* .. */ }

Does the standard require that both of these loops visit elements in the same order (assuming the container is unmodified)?

---

My analysis of this question...

I read the standard and as best I can tell the answer is "no"...

Since iterators of containers are forward, there is language that requires a==b imply that ++a==++b for forward iterators. That means two iterations will go through the same path IF they both start in the same place. This reduces the question to a different question of whether the standard requires container.begin() == container.begin(). I couldn't find any language that requires this.

Answer 1

Containers are required to implement operator==(). That is we can do:

container c;
c == c;

That relation is required to work the same as:

std::distance(a.begin(), a.end()) == std::distance(b.begin(), b.end()) &&
std::equal(a.begin(), a.end(), b.begin());

The important part here is the call to std::equal(). This call requires that two independent calls to container.begin() will produce the same sequence of values. If it didn't, then c == c would be false, and that doesn't make any sense because == is an equivalence relation.

Therefore, my answer is that we can claim that the standard requires that two passes of any container must result in the same ordering. Obviously this requirement breaks if you do anything that changes the container or invalidates iterators.

Citations:

• C++ 2011 Table 96 — Container requirements

Answer 2

I think @Sharth's conclusion is correct, but (for anybody who cares about newer standards) is already obsolete (and may not have ever reflected reality--see below).

More recent drafts of the standard (e.g., n3797) have changed the requirements, apparently intentionally removing the ordering requirement. Specifically, it says (§23.2.5/12):

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1,Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1,Eb2) obtained from b.equal_range(Ea1), such that distance(Ea1, Ea2) == distance(Eb1, Eb2) and is_permutation(Ea1, Ea2, Eb1) returns true.

I also have relatively low confidence that implementations actually meet the requirements of the 2011 standard either. In particular, the unordered containers are normally implemented as hash tables with linked lists for collision resolution. Since those linked lists are expected to be short, they're not necessarily sorted (particularly since items stored in unordered containers aren't required to define operations to be used for sorting, such as operator<). This being the case, it's fairly routine for the linked lists to hold the same items, but in an order that depends upon the order in which they were inserted.

In such a case, it would be fairly routine for two hash tables that contained the same items that had been inserted in different orders to iterate over those items in different orders.

In theory such an implementation doesn't conform with the C++11 standard--but I'd guess the change cited above was made largely because that requirement couldn't be met in practice (because, as noted above, the container had no way to enforce ordering).

So, as long as you're dealing with the same container, unchanged, depending on iteration in the same order may be safe. Two containers that have the same contents may not work out so well though (and even in what claims to be a C++11 implementation, you probably can't expect it to meet tighter requirements than the newer drafts contain).

Answer 3

My read of the standard is that this is not guaranteed. 23.2.5, paragraph 6, states:

Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified.

Let's take off the table the fairly clear guarantee that elements that hash to the same key will have their relative order preserved no matter what. That seems to be fairly clear. Additionally, lets exclude any modifications to the container. In the remaining scope:

Although this doesn't actually explicitly define that the iteration order, in absence of changes to the container, is unstable, I interpret the statement "the absolute order of elements in an unordered container is not specified" on its literal face value. If the iteration order is undefined, then it is undefined, and is not guaranteed to be the same every time.

I think it all comes down to whether, in the quoted excerpt "is not specified" should be interpreted as "it could be anything" or "it could be anything, at any given time".

I think an argument can be made either way. I would interpret "is not specified" in the most strict, literal interpretation of the latter, but I wouldn't object too hard if someone would argue in favor of the former.

Answer 4

Unordered containers do return forward iterators (which are defined in § 24.2.5) and those do have this property: a == b implies ++a == ++b. This seems to imply so long that unordered_container.begin() == unordered_container.begin() is true, that the traversal order will be the same.

I was unable to find any language that requires unordered_container.begin() == unordered_container.begin() which led me to a tentative answer of "no", the traversal order isn't required to be the same.