Creating my own Iterators

Question

I'm trying to learn C++ so forgive me if this question demonstrates a lack of basic knowledge, you see, the fact is, I have a lack of basic knowledge.

I want some help working out how to create an iterator for a class I have created.

I have a class 'Shape' which has a container of Points. I have a class 'Piece' which references a Shape and defines a position for the Shape. Piece does not have a Shape it just references a Shape.

I want it to seem like Piece is a container of Points which are the same as those of the Shape it references but with the offset of the Piece's position added.

I want to be able to iterate through the Piece's Points just as if Piece was a container itself. I've done a little reading around and haven't found anything which has helped me. I would be very grateful for any pointers.

Answer 1

/EDIT: I see, an own iterator is actually necessary here (I misread the question first). Still, I'm letting the code below stand because it can be useful in similar circumstances.

---

Is an own iterator actually necessary here? Perhaps it's sufficient to forward all required definitions to the container holding the actual Points:

// Your class `Piece`
class Piece {
private:
    Shape m_shape;

public:

    typedef std::vector<Point>::iterator iterator;
    typedef std::vector<Point>::const_iterator const_iterator;

    iterator begin() { return m_shape.container.begin(); }

    const_iterator begin() const { return m_shape.container.begin(); }

    iterator end() { return m_shape.container.end(); }

    const_iterator end() const { return m_shape.const_container.end(); }
}

This is assuming you're using a vector internally but the type can easily be adapted.

Answer 2

You should use Boost.Iterators. It contains a number of templates and concepts to implement new iterators and adapters for existing iterators. I have written an article about this very topic; it's in the December 2008 ACCU magazine. It discusses an (IMO) elegant solution for exactly your problem: exposing member collections from an object, using Boost.Iterators.

If you want to use the stl only, the Josuttis book has a chapter on implementing your own STL iterators.

Answer 3

Here Designing a STL like Custom Container is an excellent article which explains some of the basic concepts of how an STL like container class can be designed along with the iterator class for it. Reverse iterator (little tougher) though is left as an exercise :-)

HTH,

Answer 4

You can read this ddj article

Basically, inherit from std::iterator to get most of the work done for you.

Answer 5

Writing custom iterators in C++ can be quite verbose and complex to understand.

Since I could not find a minimal way to write a custom iterator I wrote this template header that might help. For example, to make the Piece class iterable:

#include <iostream>
#include <vector>

#include "iterator_tpl.h"

struct Point {
  int x;
  int y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}
  Point operator+(Point other) const {
    other.x += x;
    other.y += y;
    return other;
  }
};

struct Shape {
  std::vector<Point> vec;
};

struct Piece {
  Shape& shape;
  Point offset;
  Piece(Shape& shape, int x, int y) : shape(shape), offset(x,y) {}

  struct it_state {
    int pos;
    inline void next(const Piece* ref) { ++pos; }
    inline void begin(const Piece* ref) { pos = 0; }
    inline void end(const Piece* ref) { pos = ref->shape.vec.size(); }
    inline Point get(Piece* ref) { return ref->offset + ref->shape.vec[pos]; }
    inline bool equal(const it_state& s) const { return pos == s.pos; }
  };
  SETUP_ITERATORS(Piece, Point, it_state);
};

Then you would be able to use it as a normal STL Container:

int main() {
  Shape shape;
  shape.vec.emplace_back(1,2);
  shape.vec.emplace_back(2,3);
  shape.vec.emplace_back(3,4);

  Piece piece(shape, 1, 1);

  for (Point p : piece) {
    std::cout << p.x << " " << p.y << std::endl;
    // Output:
    // 2 3
    // 3 4
    // 4 5
  }

  return 0;
}

It also allows for adding other types of iterators like const_iterator or reverse_const_iterator.

I hope it helps.

Answer 6

The solution to your problem is not the creation of your own iterators, but the use of existing STL containers and iterators. Store the points in each shape in a container like vector.

class Shape {
    private:
    vector <Point> points;

What you do from then on depends on your design. The best approach is to iterate through points in methods inside Shape.

for (vector <Point>::iterator i = points.begin(); i != points.end(); ++i)
    /* ... */

If you need to access points outside Shape (this could be a mark of a deficient design) you can create in Shape methods that will return the iterator access functions for points (in that case also create a public typedef for the points container). Look at the answer by Konrad Rudolph for details of this approach.