What is multi-pass guarantee per C++ ISO standard?

Question

Reading Working Draft N3337-1, Standard for Programming Language C++, 24.2.5 Forward iterators, page 806.

From draft:

Two dereferenceable iterators a and b of type X offer the multi-pass guarantee if:
— a == b implies ++a == ++b and
— X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.

[ Note: The requirement that a == b implies ++a == ++b (which is not true for input and output iterators) and the removal of the restrictions on the number of the assignments through a mutable iterator (which applies to output iterators) allows the use of multi-pass one-directional algorithms with forward iterators. —end note ]

Could someone re-interpret this in easier terms ? I understand that Forward iterators are multi-pass, but I don't understand how this is accomplished per C++ standard requirements.

Answer 1

The terms states it all, I'd think: you can pass through the sequence multiple times and remember positions within the sequence. As long as the sequence doesn't change, starting at a specific position (iterator) you'll traverse over the same objects as often as you want in the same order. However, you can only go forward, there is no way to move backwards. The canonical example of a sequence like this is a singly-linked list.

The quoted clause basically says, that if you have two iterators comparing equal and you increment each one of them, you get to the same position and they compare equal again:

if (it1 == it2) {
    ++it1;
    ++it2;
    assert(it1 == it2); // has to hold for multi-pass sequences
}

The somewhat weird expression ++X(a), *a is basically intended to advance an iterator independent to a and the requirement that ++X(a), *a being equivalent to *a basically means that iterator over the sequence using an independent iterator doesn't change what a refers to. This is unlike input iterator where ++InIt(a), *a is not necessarily equivalent to *a as the first expression can have change the position, possibly invalidating a and/or change the value it is referring to.

By contrast, the single-pass sequence (input and output iterations in standard terms) can only be traversed once: trying to traverse the sequence multiple times will not work necessarily work. The canonical example of sequences like this are input from the keyboard and output to the console: once read, you can't get back the same characters again and once sent you can't undo the characters.