自定义容器的迭代器

Question

在我的项目中我有一些自定义的类，大致结构如下。

点，表示一个2D int坐标

struct Point {
  int x;
  int y;
}

线，代表两点之间绘制的线

class Line {
    Point start;
    Point end;
}

多边形，表示由点数定义的多边形。

class Polygon {
  private:
    std::vector<Point> _vertices;
}

我正在尝试为 Polygon 实现一个自定义迭代器，目标是语法类似于：

Polygon aPolygon;
Point somePoint;
for( auto line_it = aPolygon.begin(); line_it != aPolygon.end(); line_it++ ){
    if( line_it->includes(somePoint) ){
        // Do something
    }
}

在多边形上迭代时，n:th 元素将是
Line( _vertices[n], _vertices[n+1] ),
最后一个是
Line( _vertices[_vertices.size() - 1], _vertices[0] )

我如何实现这样的迭代器，或者以其他方式实现类似的语法和可接受的性能？

我正在查看类似的问题，但我还没有找到足够相似的问题来提供全面的答案。如果可能的话，我更喜欢使用 c++20 标准的 STL 解决方案。

我意识到这个问题不必要地含糊不清，更具体地说，我想问的是如何为我的迭代器实现 *、-> 和 ++ 运算符。

class Polygon {
  public:
    /* ... */

    struct PolygonIterator {
        using iterator_category = std::input_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = Line;
        using pointer = value_type*;
        using reference = value_type&;
        
        explicit PolygonIterator( Point* ptr ) : m_ptr( ptr ) {}
        reference operator*();
        // ^ Should return Line reference, but I have Point in container?
        PolygonIterator& operator++();
        pointer operator->();
        bool operator==(const PolygonIterator& other);
      private:
        Point* m_ptr;
    };
    PolygonIterator begin() { return PolygonIterator( &_vertices.front() ); }
    PolygonIterator end() { return PolygonIterator( &_vertices.back() ); }

Answer 1

再次查看您的代码，满足 前向迭代器 要求会很棘手，因为您实际上是在动态生成这些行。因此我建议做一个 input iterator.

operator++ 应该只是递增 m_ptr，没有什么异常。但是您可能希望存储 std::vector 迭代器而不是指针（然后，如果您为标准容器启用迭代器调试，它将扩展到您的迭代器）。

那么你有两个选择：

将当前的 Line 存储在迭代器中。然后 * 和 -> return 分别是一个引用和一个指向它的指针。 ++ 需要在增加 pointer/iterator 后更新此 Line。
Return operator* 的 Line 按值，并将 using reference 更改为 Line 以匹配 return 类型。这是不寻常的，但允许用于输入迭代器。

那么operator->就变得棘手了。它不能 return 一个指针（因为没有 Line 指向），所以它必须 return 一个助手 class 按值，这反过来会存储一个Line（再次按值），并将 -> 重载为 return 指向它的指针。您可能还应该更改 using pointer 以匹配此助手的类型 class.

Answer 2

欢迎来到非容器的容器世界！

从一开始，标准库容器就应该直接包含它们的对象。我可以找到 2 篇关于此的参考文章：

When Is a Container Not a Container? 作者 Herb Sutter，
To Be or Not to Be (an Iterator) 埃里克·尼布勒

长话短说你的伪容器只是一个代理容器：对象存在于别处，容器只能构建代理到他们。它并不少见，vector<bool> 就是这样一个容器，它的迭代器只是代理迭代器。简单地说，如果您查看标准库实现的源代码，您会时不时地发现 算法中 vector<bool> 的特殊处理 因为 vector<bool> 迭代器假装当它们甚至不能满足前向容器的要求时成为随机访问迭代器。

这意味着您的迭代器将只是代理迭代器，它们的引用类型将是对象（代理）而不是真正的引用。因此，它们只不过是简单的 输入迭代器 。你可以接受，这就足够了，否则你可以看看C++20的range库，它应该开始提供对代理容器和迭代器的一些支持。

自定义容器的迭代器

Iterator for custom container

c++

containers

iterator

c++20