CODEWITHSUNDEEP
c++iteratorcontainersc++20
Olgittmar
Olgittmar

Reputation: 23

Iterator for custom container

In my project I have some custom classes, with roughly the structure below.

Point, which represents a 2D int coordinate

struct Point {
  int x;
  int y;
}

Line, which represents a line drawn between two Points

class Line {
    Point start;
    Point end;
}

Polygon, which represents the polygon that is defined by number of Points.

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

I'm trying to implement a custom iterator for Polygon, the goal being a syntax something like:

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

When iterating over Polygon the n:th element would be
Line( _vertices[n], _vertices[n+1] ),
and the last would be
Line( _vertices[_vertices.size() - 1], _vertices[0] )

How do I implement such an iterator, or otherwise acheive similar syntax with acceptable performance?

I'm looking through similar questions, but I've yet to find one similar enough for a comprehensive answer. If possible I would prefer a STL solution that uses c++20 standard.

I realize the question was unecessarily vague, more specifically I'm asking how I can implement the *,-> and ++ operators for my iterator.

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() ); }

Upvotes: 1

Views: 1356

Answers (2)

Serge Ballesta
Serge Ballesta

Reputation: 148910

Welcome into the world of containers which are not containers!

Since the beginning, standard library containers are expected to actually directly contain their objects. I could find 2 reference articles about that:

Long story made short your pseudo container is only a proxy container: objects exists elsewhere, and the container can only build proxies to them. It is not so uncommon and vector<bool> is such a container, and its iterators are only proxy iterators. Simply if you look into the sources of an implementation of the standard library, you will find every now and then special processing for vector<bool> in algorithm because vector<bool> iterators pretend being random access iterators when they cannot even meet the requirements of a forward container.

That means that your iterators will only be proxy iterators and their reference type will be an object (the proxy) instead of a true reference. Because of that they will be no more than simple input iterators. It is is acceptable for you, that will be enough, else you could have a look to the range library of C++20, which should start to provide some support to proxy containers and iterators.

Upvotes: 1

HolyBlackCat
HolyBlackCat

Reputation: 96236

Looking at your code again, satisfying forward iterator requirements would be tricky, because you essentially generate the lines on the fly. Hence I suggest making an input iterator.

operator++ should just increment m_ptr, nothing unusual. But you might want to store an std::vector iterator instead of a pointer (then, if you enable iterator debuggning for standard containers, it will extend to your iterators).

Then you have two options:

  1. Store the current Line inside of the iterator. Then * and -> return a reference and a pointer to it respectively. ++ will need to update this Line after incrementing the pointer/iterator.

  2. Return the Line from operator* by value, and change using reference to Line to match the return type. This is unusal, but allowed for input iterators.

    Then operator-> becomes tricky. It can't return a pointer (because there's no Line to point to), so it has to return a helper class by value, which in turn would store a Line (again by value), and overload -> to return a pointer to it. You probably should also change using pointer to match the type of this helper class.

Upvotes: 1

Related Questions