2

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?

M.M
  • 138,810
  • 21
  • 208
  • 365
Daniel
  • 7,357
  • 7
  • 32
  • 84
  • 3
    I think it should be the same although I cannot find where in the Standard it is spelled out – M.M Nov 14 '18 at 00:44

3 Answers3

6

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.

T.C.
  • 133,968
  • 17
  • 288
  • 421
  • Maybe the [DS9000](http://enacademic.com/dic.nsf/enwiki/2748465) could detect that there are never two such iterators simultaneously in existence (we go begin...end, then begin...end again in the question) and give a different ordering the second time, without actually breaking any of the rules – M.M Nov 14 '18 at 01:02
2

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.

Gregory Currie
  • 607
  • 4
  • 14
  • The guarantee may be weak from a standards perspective, but any reasonable implementation has this guaranteed. After all, the state of the unordered_set does not change because a call to begin() and end(). – Captain Giraffe Nov 14 '18 at 00:51
-1

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.

Cagri Candan
  • 90
  • 1
  • 9