Does repeated iteration through an unordered_set produce consistent results?

Question

Let's say I have an unordered_set<int> S.

I know I can iterate through S with:

void iterate(){
    for (const auto& elem: S) {
        cout<<elem<<endl;
    }
}

My question is: if I call iterate() and it prints a certain sequence of numbers, is it guaranteed that if I call iterate() as many times as I want, it will always print the same sequence?

Answer 1

Yes, as long as S is not modified. [container.requirements.general]p6:

begin() returns an iterator referring to the first element in the container.

The use of the definite article "the" implies that there's only one such "first element". Therefore, multiple calls to begin() on the same (unchanged) container must return iterators referring to the same element.

Additionally, all container iterators are required to be at least forward iterators (see Table 64 in the same subclause).

The rest falls out the forward iterator requirements in [forward.iterators], in particular:

• two dereferenceable iterators compare equal if and only if the results of dereferencing them are bound to the same object; and
• incrementing two equal iterators produces equal iterators.

Since you start with equal iterators, every step of the iteration must produce equal iterators, which must refer to the same element in the container.