前向迭代器的多遍保证强度

Question

考虑标准中前向迭代器的定义（草案 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.

多次通过保证的目的似乎是允许这样的代码：

*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 <---------------------------------------------------

然而，从形式上讲，多次通过保证似乎只意味着执行 iter 的副本并递增副本会使 *iter 保持不变，而随后的第二次递增 iter_copy 可能会改变 *iter.

现在您的第一个想法可能是"duh, induction!"，但似乎达不到预期的结果；它只是说，如果我们复制 iter_copy 并增加那个副本，那么 *iter_copy 不变，但它没有说明原始 *iter .

问题：是否可以证明指定的多次通过保证意味着什么？

Answer 1

当然，可能提出一种满足所有前向迭代器保证但不是完美多遍的类型。

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]; }
};

让我们看一下要求：

a == b 表示 ++a == ++b。查看。 operator++() 甚至不影响平等。
(void)*a, *a 等同于 *a。检查，取消引用没有破坏性。
(void)++X(a), *a 等同于 *a。查看。递增 1 会更改 other int，而不是此迭代器当前 "points" 的那个。所以这个条件也成立。
a == b 当且仅当 *a 和 *b 绑定到同一个对象。查看。

但是，(void)++++X(a), *a绝对不等同于*a。您会得到相同的 int，只是大了一个。

事实上，我可以想出一个不符合保证的可笑的不切实际的迭代器，这可能表明有一个实际实用的迭代器也不符合保证。那里有很多 C++。

前向迭代器的多遍保证强度

Strength of the multi-pass guarantee for forward iterators

c++

c++-standard-library

language-lawyer