Fast and flexible iterator for abstract class

Question

In order to traverse grids with data in a fast and flexible way I set up an abstract, templated GridDataStructure class. The data should be accessed by STL iterators. When someone uses the class, he should not worry about which kind of STL iterator is appropriate for a specific subclass.

A solution to this problem seems to be http://stackoverflow.com/questions/2191724/using-iterators-to-hide-internal-container-and-achieve-generic-operation-over-a-b. However, I do not get why the begin() and end() members are not virtual anymore. Next to that I could not figure out where exactly the necessary methods for the STL iterator class (like operator++, operator* etc.) should be implemented.

Could you please have a look whether or not I make a design mistake? Important to me is a flexible design, but not at the cost of performance.

My class design:

template<class T>
class GridDataStructure
{
public:
    virtual iterator begin() = 0;
    virtual iterator end() = 0;
};

template<class T>
class GridDataUniform : GridDataStructure
{
public:
    GridDataUniform(int size);        

    iterator begin();
    iterator end();

    class iterator : public std::iterator<std::forward_iterator_tag, T> {
    public:
      iterator(Node* p) : node_(p) {}
      ~iterator() {}

      iterator& operator=(const iterator& other);
      bool operator==(const iterator& other);
      bool operator!=(const iterator& other);
      iterator& operator++();
      iterator& operator++(int);
      T& operator*();
      T* operator->();

    private:
      Node* node_;
    };

    private:
        T* griddata;
};

I would like to access my grid container in STL style, like:

GridDataStructure<int>::iterator = someGrid->begin(); // where someGrid is an instance of GridDataUniform
std::cout << *(iter) << std::endl;

Any help is highly appreciated.

Edit (19.10.10): Added nested iterator class

Edit (20.10.10): Added code:

template<class T>
class GridDataStructureBase
{
protected:
class BaseIteratorImpl
{
    virtual iterator begin() = 0;
    virtual iterator end() = 0;
    virtual iterator& operator++() = 0;
}

public:
class iterator : std::iterator<std::forward_iterator_tag, T>
{
public:
    iterator(const BaseIteratorImpl& itImpl) {}
    iterator begin() { return itImpl->begin(); }
    iterator end() { return itImpl->end(); }
    iterator& operator++() { return itImpl->operator++() }

private:
    BaseIteratorImpl* itImpl;

};

iterator begin()
{
    iterator* i = new iterator(??);
    return i->begin();
}

iterator end()
{
    return iterator(NULL);
}

};

Answer 1

In the solution, begin and end don't need to be virtual, because they just call BaseIteratorImpl::begin and BaseIteratorImpl::end which are virtual.

In your specific case, you could just make begin and end virtual and not do any forwarding and it would be able to do what you want. The solution you pointed to is if you want different style iterators over the same structure, not just structure-iterator pairings which it seems you want.

EDIT: Here's something to start with (not tested or even compiled) -- might not compile and will leak (write destructors, copy ctors, op=, where you need to) -- just to get you started on the idea.

template <class T>
class GridIteratorImplBase {
   public:
      virtual GridIteratorImplBase<T>& operator++() = 0;
      virtual T& operator*() = 0;
};

template <class T>
class GridIterator {
   private:
      GridIteratorImplBase<T> *baseImpl;
   public:
      GridIterator(GridIteratorImplBase<T> *b) :baseImpl(b) {}
      GridIterator& operator++() { baseImpl->operator++(); return *this;}
      T& operator*() { return baseImpl->operator*(); }


  // you need to write a dtor, copy ctor and op= or this will leak
  // copy ctor and op= need to make new objects that are copies of baseImpl, dtor needs to delete -- make sure not to share baseImpl between two GridIterator objects
};


template <class T>
class Grid {
   virtual GridIterator<T> begin() = 0;
   virtual GridIterator<T> end() = 0;
};


template <class T>
class GridUniform {

  template <class T>
  class GridUniformIterator : GridIteratorImplBase<T>
      private T* current;
   public:
      GridUniformIterator(T* c) : current(c) {}
      virtual GridIteratorImplBase<T>& operator++() { current++; return *this; }
      virtual T& operator*() { return *current; }
  };

  GridIterator<T> begin() { 
      GridIterator<T> iter(new GridUniformIterator(gridData)); 
      return iter; 
  }
  GridIterator<T> end() { 
      GridIterator<T> iter(new GridUniformIterator(gridData+size));
      return iter; 
  }


  private:
    T* gridData;
    int size;
};

I typed this directly in to the text area of this answer -- not a compiler. It's meant to give you the idea so you can get started.

1. begin and end are supposed to create iterators
2. iterators need to be able to be copy constructed and have operator= called on them. If you try to have one base class for them, they will get casted to the base, so you can't use virtual for them
3. To get around #2, you make iterators just hold onto a pointer to a base class of an iterator implementation.