c++ - 输入/输出迭代器的不等运算符的要求

Question

我正在创建一个基于图 block 的小型游戏。游戏中的元素将它们的位置存储在桶矩阵中。我将其实现为一个名为 Grid 的类模板，其中包含一个名为 Tile 的桶类。

Grid 本质上只是 std::vector 的包装器，具有各种访问器方法，可将坐标转换为索引键。它还转发 vector 的迭代器，以便我可以遍历 Grid 中的所有 Tiles。

尽管有时我只需要遍历 Grid 的一个子部分。所以我实现了一个名为 Section 的小类，它在构造函数中采用两组坐标来定义 AABB。 Section 的 begin() 和 end() 方法返回输入/输出迭代器，用于循环遍历 AABB 内的所有图 block 。

一切正常，但我试图使迭代器的性能尽可能接近嵌套循环。基本上使用基于 Section 的范围应该不会比以下贵太多:

for (size_t y = 0, end_y = NUM; y < end_y; ++y)
{
    for (size_t x = 0, end_x = NUM; x < end_x; ++x)
    {
        auto& tile = grid[coords_to_key(x, y)];
    }
}

这让我进入了问题的重点。我希望不等式运算符尽可能简单，所以我这样实现了它:

bool operator!=(const Section_Iterator& other) const
{
    return m_coords.y < other.m_coords.y;
}

由于迭代器按顺序扫描 Section 中的每一行，因此当 iterator.y >= end.y 时，我们知道我们已经“结束”。这意味着我的不等式运算符适用于基于范围的 for 循环，因为在引擎盖下它们只是检查 iterator != end。

虽然运算符的实现看起来很奇怪。就像真的很奇怪。 例如iterator !=++iterator 可能是真也可能是假。这取决于预增量是否导致迭代器跳转到下一行。

我一直在研究这个标准，我认为我是清楚的，因为他们区分了平等和等价。

来自 http://en.cppreference.com/w/cpp/concept/InputIterator

Note, "in the domain of ==" means equality comparison is defined between the two iterator values. For input iterators, equality comparison does not need to be defined for all values, and the set of the values in the domain of == may change over time.

来自 http://en.cppreference.com/w/cpp/concept/OutputIterator

Equality and inequality may not be defined for output iterators. Even if an operator== is defined, x == y need not imply ++x == ++y.

老实说，标准语让我头晕目眩。我的行为合法吗？

Answer 1

经过更多研究后发现，根据标准，我所做的是不合法的。

输入迭代器必须是 EqualityComparable .这意味着:

• For all values of a, a == a yields true.
• If a == b, then b == a
• If a == b and b == c, then a == c

使用我当前的相等运算符 a == b 并不意味着 b == a。

为了解决我的问题，我查看了 std::istream_iterator ，它是输入迭代器的实现，自然它所做的任何事情都必须符合标准。它的相等运算符的行为描述如下:

Checks whether both lhs and rhs are equal. Two stream iterators are equal if both of them are end-of-stream iterators or both of them refer to the same stream

基本上，如果两个迭代器都有效，则它们比较相等。如果他们都“过了最后”，他们比较相等。如果一个是有效的，但另一个是“结束”，则它们不相等。

将相同的逻辑应用到我的 Section::iterator 很容易。迭代器现在包含一个 bool 值 m_valid。方法 begin() 总是返回一个迭代器，其中 m_valid == true 而 end() 方法总是返回一个迭代器，其中 m_valid == 假。

迭代器的预递增运算符现在测试它是否已经结束并相应地设置 bool 值。

Section_Iterator& operator++()
{
    ++m_coords.x;
    if (m_coords.x >= m_section.m_max.x)
    {
        m_coords.x = m_section.m_min.x;
        ++m_coords.y;
        m_valid = (m_coords.y < m_section.m_max.y);
    }

    return *this;
}

相等运算符现在非常容易理解并且具有一致的行为。任何指向 Section 中的 Tile 的迭代器都是有效的，并且与任何其他有效的迭代器进行比较。

bool operator==(const Section_Iterator& other) const
{
    return m_valid == other.m_valid;
}

bool operator!=(const Section_Iterator& other) const
{
    return m_valid != other.m_valid;
}