C++如何为向量的向量构建迭代器

Question

我有一个二维数组，我已经将其实现为std :: vector的std :: vector，如下所示：

struct Cell
{};

struct Column
{ std::vector<Cell*> m_column; };

struct Grid
{ std::vector<Column> m_grid; }

我想为Grid构建一个输入迭代器类，这样你就可以这样做...

for (const auto cell : grid)
    cell->doSomething();

...并使用其他STL算法。但我不确定如何制作迭代器增量函数。

目前为止，我有以下内容：

struct Grid
{
    std::vector<Column> m_grid;

    struct ConstIterator
    {
        using value_type = const Cell*;
        using reference = const Cell*&;
        using pointer = const Cell**;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::input_iterator_tag;

        reference operator* () { return curr; }

        ConstIterator& operator++ () { incrementAcrossGrid(); return *this; }
        ConstIterator operator++(int) { const auto temp(*this); incrementAcrossGrid(); return temp; }

        bool operator== (const ConstIterator& that) { return curr == that.curr; }
        bool operator!= (const ConstIterator& that) { return !(*this == that); }

        void incrementAcrossGrid()
        {
            // ???
        }

        const Cell* curr;
    };

    ConstIterator begin() const { return { m_grid.front().m_column.front() }; }
    ConstIterator end() const { return { m_grid.back().m_column.back() + 1 }; } // Is there a better way to get the end?
};

如您所见，我不确定在incrementIterator()里应该放什么。增加它直到达到列的末尾很容易，但我不知道如何将其从一列底部指向下一列顶部。

也许我的方法完全错误，所以所有建议都受欢迎（包括Boost库等）。重要的是我需要能够使用Grid::begin()和Grid::end()来遍历单元格。

- Liam Goodacre

---

提示：你需要在迭代器类中存储两个迭代器。一个用于遍历 std::vector<Column>，另一个用于遍历当前Column中的std::vector<Cell*>。 - Yksisarvinen

Answer 1

基本思路是在自定义迭代器中保留两个迭代器：

struct Iterator {
    reference operator* () { 
        return *cell_iterator;
    }

    Iterator& operator++() {
        if (++cell_iterator == col_iterator->m_column.end()) {
            ++col_iterator;
            cell_iterator = col_iterator->m_column.begin();
        }
        return *this;
    }

    bool operator==(const Iterator& that) const {
        return col_iterator == that.col_iterator && 
               cell_iterator == that.cell_iterator;
    }
    
    std::vector<Cell*>::iterator  cell_iterator;
    std::vector<Column>::iterator col_iterator;
};

auto Grid::begin() -> Iterator {
    return Iterator{m_grid.begin()->m_column.begin(), m_grid.begin()};
}

这只是一个想法。你需要思考如何正确表示 Grid::end() 迭代器，并对 operator++() 进行必要的更改。当 col_iterator 到达 m_grid.end() 时，你就不能再进行解引用以获取下一个 cell_iterator。

- Evg

---

谢谢您的回答！如果没有您的帮助，我自己可能要花很长时间才能想出来。我不太清楚std::vector::iterator是什么。在我的代码中，我使用了一个原始指针来指向Cell。在这里，std::vector::iterator是方便还是必需品？我问这个问题是因为实际上我并没有使用std::vector，而是JUCE::OwnedArray，它似乎没有相应的“iterator”子类。是否有可能找到解决方法，或者我应该使用std::vector而不是JUCE::OwnedArray？ - Liam Goodacre

@LiamGoodacre，这只是一种方便的做法。像std::vector这样的连续存储迭代总是可以使用普通指针执行。OwnedArray::begin和OwnedArray::end返回ObjectClass*。只需用T*替换std::vector<T>::iterator即可。注意：如果m_column确实保存指针而不是Cell对象本身，则不是Cell*，而是Cell**。 - Evg

@zaep 你是正确的，我答案中的代码有误。但是你的方法存在一个问题，当你到达最后一行的最后一个像素时，下一次应用 operator++ 将会将 line_iter 设置为结束迭代器，并在其上执行 ->begin() 是未定义的行为。即使您从未引用所得到的迭代器，也不能执行 line.end()->begin()。 - Evg

我已经对越过末尾单元格迭代器进行了更正，但是关于表示超出最后一个元素的问题仍需解决。 - Evg

@zaep 它可能以写入未分配的内存的方式工作。但是，如果您启用调试迭代器（例如在GCC中使用-D_GLIBCXX_DEBUG），则会引发异常。 - Evg