input/output 迭代器的不等运算符的要求

Question

我正在创建一个基于方块的小游戏。游戏中的物品将它们的位置存储在桶矩阵中。我将其实现为一个名为 Grid 的 class 模板，其中包含一个名为 Tile.

的存储桶 class

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

中的所有 Tiles

虽然有时我只需要遍历 Grid 的一个小节。所以我实现了一个名为 Section 的小 class，它在构造函数中采用两组坐标来定义 AABB。 Section return input/output 迭代器的 begin() 和 end() 方法，用于遍历 AABB 内的所有图块。

一切正常，但我试图使迭代器的性能尽可能接近嵌套循环。基本上使用基于 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 时我们是 'past the end'。这意味着我的不等式运算符适用于基于范围的 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

老实说，我不知道你上面的做法是否合法。尽管它是合法的，但它确实有奇怪的语义。

相反，我会考虑这样的事情来解决你的问题：

#include <iostream>
#include <vector>

struct Grid
{
    std::vector<int> tiles;
    size_t rows;
    size_t cols;
};

class SectionIterator
{
public:
    SectionIterator(Grid * grid, size_t row, size_t col, size_t endRow) :
            m_row{ row },
            m_col{ col },
            m_startRow{ row },
            m_endRow{ endRow },
            m_grid{ grid }
    {
    }

    SectionIterator & operator++()
    {
        ++m_row;
        if (m_row == m_endRow)
        {
            m_row = m_startRow;
            ++m_col;
        }
        return *this;
    }

    bool operator==(const SectionIterator & other) 
    {
        return (m_grid == other.m_grid) 
                && (m_row == other.m_row)
                && (m_col == other.m_col);
    }

    bool operator!=(const SectionIterator & other) 
    {
        return !(*this == other);
    }

    int & operator*() 
    {
        return m_grid->tiles[m_col * m_grid->rows + m_row];
    }

    int * operator->() 
    {
        return &operator*();
    }
private:
    size_t m_row;
    size_t m_col;
    size_t m_startRow;
    size_t m_endRow;
    Grid * m_grid;

};

struct Section 
{
    SectionIterator m_begin;
    SectionIterator m_end;

    SectionIterator begin() { return m_begin; }
    SectionIterator end() { return m_end; }
};

int main() 
{
    Grid grid{ std::vector<int>{ 1, 2, 3, 4, 5, 6 }, 2, 3 };
    // 1, 3, 5 
    // 2, 4, 6

    // look up start and end row and col
    // end positions are found by looking up row/col of section end and then adding one
    size_t startRow = 0;
    size_t endRow = 2;
    size_t startCol = 1;
    size_t endCol = 3;

    SectionIterator begin = SectionIterator{ &grid, startRow, startCol, endRow };
    // Note that the end iterator actually has startRow as its startRow, not endRow, because operator++ will set the iterator's m_row back to startRow so this will make it equal the end iterator once the iteration is complete
    SectionIterator end = SectionIterator{ &grid, startRow, endCol, endRow };
    for (int v : Section{ begin, end })
    {
        std::cout << v << std::endl;
    }
    return 0;
}

请注意，这假定您有一些函数可以在您的坐标和网格中的 row/col 索引之间进行转换。此外，上面以列优先顺序迭代，但可以很容易地更改为以行优先顺序迭代。

编辑

为了阐明从浮点坐标到索引的转换是如何工作的，请考虑以下内容。

我假设您的图块定义为每个图块覆盖一个 1x1 正方形的浮点坐标。例如，tile (0, 0) 覆盖浮点区间 [0.0, 1.0), [0.0, 1.0)，tile (2, 2) 覆盖区间 [2.0, 3.0), [2.0, 3.0)。我相信这就是您描述当前设置的方式。

如果您希望遍历从 (1.2, 1.2) 到 (4.2, 4.2) 的部分中的所有图块，首先通过截断将这些点转换为行、列索引：

(1.2, 1.2) = 平铺 (1, 1) (4.2, 4.2) = 瓷砖 (4, 4)

这意味着你想迭代闭-闭区间[1, 4]中的行和闭-闭区间[1, 4]中的列。由于像上面这样的迭代器使用闭-开区间，您必须将 1 添加到结束索引，这样您传递给迭代器的值代表行的区间 [1, 5) 和列的区间 [1, 5)。注意这些区间其实和闭闭区间形式是一样的，只是端值表示"one past the last index you want to dereference".

编辑#2

您表示您确实希望确保您的部分在浮点坐标中的开区间结束，以便 (1.0, 1.0) 到 (4.0, 4.0) 包含 3 个平铺行和 3 个平铺列，而不是4.

您可以通过将结束索引与原始值进行比较，如果不是整数则只加 1，因此

float coord = ...;
size_t idx = static_cast<size_t>(coord);
constexpr float tolerance = 1e-6f;
if (std::abs(coord - idx) > tolerance)
{
    // Add 1 to make the range include the last tile
    ++idx;
}

Answer 2

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

输入迭代器必须是 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

基本上，如果两个迭代器都有效，则它们比较相等。如果它们都是 'past the end'，则它们比较相等。如果一个有效但另一个是 'past the end' 它们不相等。

对我的 Section::iterator 应用相同的逻辑很容易。迭代器现在包含一个布尔值 m_valid。方法 begin() 总是 returns 一个迭代器，其中 m_valid == true 和 end() 方法总是 returns 一个迭代器，其中 m_valid == false.

迭代器的预递增运算符现在测试它是否已经结束并相应地设置 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;
}

input/output 迭代器的不等运算符的要求

Requirements of the inequality operator of an input/output iterator

c++

iterator

equality

equivalence