Does repeated iteration through an unordered_set produce consistent results?

user_5348875 0
Viewed 157

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?

unordered-set c++
3 Answers

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.

user_27567190

Provided that you do not change the contents of the set, you will get the same order of elements during iteration.

This is because iteration is deterministic. Should the internal structure of the set change for no reason, iterators would get invalidated.

user_36153930

I found a sentence which is "Notice that an unordered_set object makes no guarantees on which specific element is considered its first element." in this website I belive this can help your question.

user_29260440
Related