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

Question

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

6

考虑标准中关于前向迭代器的定义（草案n4659，[forward.iterators]/27.2.5）：

一个类或指针类型 X 满足前向迭代器的要求，如果

- X 满足输入迭代器的要求（27.2.3）， - X 满足默认构造函数的要求（20.5.3.1）， - 如果 X 是可变迭代器，则 reference 是一个指向 T 的引用；如果 X 是常量迭代器，则 reference 是一个指向 const T 的引用， - 表97中的表达式有效并具有指示的语义，并且 - X 类型的对象提供多遍保证（multi-pass guarantee），如下所述。 [省略注释] 如果两个可解引用迭代器 a 和 b 的类型是 X，则当且仅当： - a == b 意味着 ++a == ++b，且 - X 是指针类型或者表达式 (void)++X(a), *a 等价于表达式 *a。

注意：对于前向迭代器，要求 a == b 意味着 ++a == ++b（这对于输入和输出迭代器不成立），并且去除了可变迭代器上的赋值次数限制（这适用于输出迭代器），这使得可以使用多遍单向算法与前向迭代器。—— 注

[表97省略]

- 如果 a 和 b 相等，则 a 和 b 都可解引用，或者都不可解引用。 - 如果 a 和 b 都可解引用，则当且仅当 *a 和 *b 绑定到同一对象时，a == b。

多遍保证的意图似乎是允许类似以下代码：

*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，归纳！”，但它似乎没有达到期望的结果；它只是说如果我们复制 iter_copy 并增加那个副本，那么 *iter_copy 不变，但并没有说明原始的 *iter。

问题：是否有可能显示所指定的多遍保证意味着预期的结果？

- Bruno

需求并没有说 *iter_copy 保持不变，它说的是 *iter 保持不变。 - Barry

请注意，(void)++(++X(a)), *a 等同于 *a 是不正确的；如果 a 是 end() 前一项，则双重增量会导致未定义行为，因此第一个是未定义的，而第二个不是。但是，如果 *iter_copy 不能使 *a 失效，则 (void)++X(iter_copy), *iter_copy 也不会失效，因为两者是等价的。 - Yakk - Adam Nevraumont

@Yakk 但是超出末尾的迭代器是不可解引用的，要求是“如果a和b是可解引用的，则…” - Bruno

但它真的是这样说的吗？（忽略对void的强制转换，这只是因为逗号运算符，假设所有迭代器都有效，因此没有超出边界的情况）它说如果我有iter并复制一个iter_copy，然后在++iter_copy之后，*iter不会改变。然后我可以再复制一个iter_copy_copy，增加iter_copy_copy，要求是*iter_copy不变。但我觉得原始的*iter没有被提及。它可能已经被第二次增量改变了... - Bruno

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Barry · Accepted Answer

当然，可以设计一种类型，满足所有前向迭代器的保证，但并不完全支持多次遍历。

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。检查通过。增加一个会改变另一个 int，而不是这个迭代器当前“指向”的 int。因此，该条件也成立。
a == b 当且仅当 *a 和 *b 绑定到同一个对象时成立。检查通过。

然而，(void)++++X(a), *a 明显不等同于 *a。你将得到相同的 int，只是它会增加一个。

我能想出一个滑稽的、不切实际的迭代器，它并不符合保证，这可能表明有一个实际的迭代器也不符合保证。C++ 世界里有很多东西。