Strength of the multi-pass guarantee for forward iterators

Question

Consider the definition of Forward iterators in the standard (draft n4659, [forward.iterators]/27.2.5):

A class or pointer type X satisfies the requirements of a forward iterator if

• X satisfies the requirements of an input iterator (27.2.3),
• X satisfies the DefaultConstructible requirements (20.5.3.1),
• If X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T,
• The expressions in Table 97 are valid and have the indicated semantics, and
• Objects of type X offer the multi-pass guarantee, described below. [note omitted] 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 ]

[table 97 omitted]

• If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.
• If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

The intent of the multi-pass guarantee seems seems to be about allowing code like:

*iter <---------------------------------------------------
X iter_copy(iter);                                       |
/* do something with iter_copy */                        |
++iter_copy; ... ++iter_copy;                            |
/* iter has not changed, and *iter now is equivalent     |
 * to *iter before the operations on iter_copy */        |
*iter <---------------------------------------------------

However formally the multi-pass guarantee only seems to imply that doing a copy of iter and incrementing the copy leaves *iter unchanged, and a second subsequent increment to iter_copy might change *iter.

Now your first thought might be "duh, induction!", but it seems to fall short of the desired result; all it says is if we do a copy of iter_copy and increment that copy, then *iter_copy is unchanged but it says nothing about the original *iter.

Question: Is it possible to show that the multi-pass guarantee as specified implies what is intended ?

Answer 1

Sure, it's possible to come up with a type that meets all the forward iterator guarantees but isn't perfectly multi-pass.

class Evil {
    int* p;
    size_t idx;

public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = int;
    using pointer = int*;
    using reference = int&;

    Evil() : p(nullptr), idx(0) { }
    Evil(int* p, size_t idx) : p(p), idx(idx) { }
    Evil(Evil const& ) = default;
    Evil& operator=(Evil const& ) = default;
    ~Evil() = default;

    // only p participates in comparison
    bool operator==(Evil const& rhs) const {
        return p == rhs.p && idx % 2 == rhs.idx % 2; 
    }
    bool operator!=(Evil const& rhs) const { return !(*this == rhs); }

    // incrementing is sort of destructive
    Evil& operator++() {
        ++idx;
        ++p[idx % 2];
        return *this;
    }
    Evil operator++(int) {
        auto tmp = *this;
        ++*this;
        return tmp;
    }

    int& operator*() { return p[idx % 2]; }
};

Let's go through the requirements:

• a == b implies ++a == ++b. Check. operator++() doesn't even affect equality.
• (void)*a, *a is equivalent to *a. Check, dereferencing isn't destructive.
• (void)++X(a), *a is equivalent to *a. Check. Incrementing one changes the other int, not the one this iterator currently "points" to. So this condition also holds.
• a == b iff *a and *b are bound to the same object. Check.

However, (void)++++X(a), *a is definitely not equivalent to *a. You'll get the same int back, it'll just be one larger.

The fact that I can come up with a comically impractical iterator that doesn't meet the guarantee might suggest that there's an actual practical one that also doesn't meet the guarantee. There's a lot of C++ out there.