nonstandard iterator for subclass with containers of subclasses

Question

Apologies that this is pretty long, but I couldn't figure out how to make it shorter and still show the important features of my problem.

I'm asking this even though I have come up with an idea of how to do what I want, but it requires implementing an iterator in a way that doesn't match the standard iterator pattern. I would like to ask for any suggestions on how this could be done in a more standard or better way.

I have an abstract base class. Any subclass of it will have some collections of objects. There is some common code that I would like to put in the base class that needs to iterate over all of the objects in the collections. The objects in the collections will all descend from another abstract base class, but will be subclass objects. There may be multiple collections of objects from multible subclasses, and the collections may be different collection types. What I'd really like to do is something like this: (Note: this code will not compile.)

class CollectionObjectBase
{
public:

  virtual int someInterface(int x) = 0;
};

class MyObjectBase
{
public:

  class iterator
  {
  public:

    virtual CollectionObjectBase& operator*() = 0;

    virtual iterator& operator++() = 0;

    virtual bool operator!=(iterator& other) = 0;
  };

  virtual iterator begin() = 0;

  virtual iterator end() = 0;

  int processCollections()
  {
    iterator it;
    int      sum = 0;

    for(it = begin(); it != end(); ++it)
      {
        sum += (*it).someInterface(7);
      }

    return sum;
  }
};

And then I want some subclasses of CollectionObjectBase and MyObjectBase like this:

class CollectionObject1 : public CollectionObjectBase { ... }
class CollectionObject2 : public CollectionObjectBase { ... }
class CollectionObject3 : public CollectionObjectBase { ... }

class MyObjectA : public MyObjectBase
{
public:

  std::map<int, CollectionObject1> someThings;
  std::vector<  CollectionObject2> otherThings;

  class iterator : public MyObjectBase::iterator
  {
  public:

    std::map<int, CollectionObject1>::iterator it1;
    std::vector<  CollectionObject2>::iterator it2;

    // Iterate first over it1 and then over it2.
    ...
  };

  virtual MyObjectBase::iterator begin()
  {
    return iterator(someThings.begin(), otherThings.begin());
  }

  virtual MyObjectBase::iterator end()
  {
    return iterator(someThings.end(), otherThings.end());
  }
};

class MyObjectB : public MyObjectBase
{
public:

  std::vector<CollectionObject1> someThings;
  std::set<   CollectionObject3> otherThings;

  class iterator : public MyObjectBase::iterator
  {
  public:

    std::vector<CollectionObject1>::iterator it1;
    std::set<   CollectionObject3>::iterator it2;

    // Iterate first over it1 and then over it2.
    ...
  };

  virtual MyObjectBase::iterator begin()
  {
    return iterator(someThings.begin(), otherThings.begin());
  }

  virtual MyObjectBase::iterator end()
  {
    return iterator(someThings.end(), otherThings.end());
  }
};

There are some big problems with the above code. First, MyObjectBase::begin() and MyObjectBase::end() can't return MyObjectBase::iterator because MyObjectBase::iterator is an abstract class, and you wouldn't want to anyway because you actually want a subclass of MyObjectBase::iterator that knows how to iterate over the collections in the subclass of MyObjectBase. You need to return a reference to MyObjectBase::iterator.

The second problem comes with MyObjectA::iterator::operator!=(). You'd like to do something like this:

virtual bool operator!=(iterator& other)
{
  return it1 != other.it1 || it2 != other.it2;
}

But to be an overload of MyObjectBase::iterator::operator!=() it has to take a parameter of type MyObjectBase::iterator& and that doesn't have members it1 and it2. My best idea I've thought of to resolve this is to replace operator!=() with a function atEnd(), since the only thing it is being used for in this code is to detect if the iterator is at the end, but it makes it really non-standard.

Finally, MyObjectA::begin() and MyObjectA::end() cannot return a temporary. Remember, we have to return a reference to a MyObjectBase::iterator that points to a MyObjectA::iterator, not copy construct a MyObjectBase::iterator. My best idea I've thought of to resolve this is to allocate the iterator with new, and when I do that I need to return a pointer, not a reference so that the caller can delete it. So here's my final code. It works and performs the function of an iterator, but it is non-standard. Can anyone think of a way to do this with an iterator that fits the standard pattern?

#include <map>
#include <vector>

class CollectionObjectBase
{
public:

  virtual int someInterface(int x) = 0;
};

class MyObjectBase
{
public:

  class iterator
  {
  public:

    virtual CollectionObjectBase& operator*() = 0;

    virtual iterator& operator++() = 0;

    virtual bool atEnd() = 0;
  };

  virtual iterator* begin() = 0;

  int processCollections()
  {
    iterator* it;
    int       sum = 0;

    for (it = begin(); !it->atEnd(); ++it)
      {
        sum += (**it).someInterface(7);
      }

    delete it;

    return sum;
  }
};

class CollectionObject1 : public CollectionObjectBase
{
public:

  virtual int someInterface(int x)
  {
    return x + 1;
  }
};

class CollectionObject2 : public CollectionObjectBase
{
public:

  virtual int someInterface(int x)
  {
    return x + 2;
  }
};

class MyObjectA : public MyObjectBase
{
public:

  std::map<int, CollectionObject1> someThings;
  std::vector<  CollectionObject2> otherThings;

  class iterator : public MyObjectBase::iterator
  {
  public:

    std::map<int, CollectionObject1>::iterator it1;
    std::map<int, CollectionObject1>::iterator it1End;
    std::vector<  CollectionObject2>::iterator it2;
    std::vector<  CollectionObject2>::iterator it2End;

    iterator(std::map<int, CollectionObject1>::iterator it1Init, std::map<int, CollectionObject1>::iterator it1EndInit,
             std::vector<  CollectionObject2>::iterator it2Init, std::vector<  CollectionObject2>::iterator it2EndInit) :
      it1(it1Init),
      it1End(it1EndInit),
      it2(it2Init),
      it2End(it2EndInit)
    {
      // Initialization handled by initialization list.
    }

    virtual CollectionObjectBase& operator*()
    {
      if (it1 != it1End)
        {
          return (*it1).second;
        }
      else
        {
          return *it2;
        }
    }

    virtual iterator& operator++()
    {
      if (it1 != it1End)
        {
          ++it1;
        }
      else
        {
          ++it2;
        }

      return *this;
    }

    virtual bool atEnd()
    {
      return it1 == it1End && it2 == it2End;
    }
  };

  virtual MyObjectBase::iterator* begin()
  {
    return new iterator(someThings.begin(), someThings.end(), otherThings.begin(), otherThings.end());
  }
};

There's an issue with useless' answer. Consider these subclasses of Impl and Base:

class MyImpl : public Base::Iterator::Impl {
public:
  MyImpl(std::vector<CollectionObjectSub>::iterator itInit) : it(itInit) {}
  CollectionObjectBase& operator*() { return *it; }
  void operator++() { ++it; }
//  bool operator==(Base::Iterator::Impl const &other) const { it == other.it; }
  bool operator==(MyImpl const &other) const { it == other.it; }
private:
  std::vector<CollectionObjectSub>::iterator it;
};

class Sub : public Base {
public:
  Iterator& begin() { return Iterator(new MyImpl(collection.begin())); }
private:
  std::vector<CollectionObjectSub> collection;
};

Sub contains a vector and MyImpl contains a vector iterator. I'd like to instantiate a Base::Iterator with impl_ pointing at a MyImpl. If MyImpl::operator== takes a MyImpl& then it isn't overloading Base::Iterator::Impl::operator==, but if it takes a Base::Iterator::Impl& then I can't access the vector iterator even if it actually is a MyImpl.

It seems like I need to do a dynamic cast to get a MyImpl, which requires RTTI. I've heard to avoid using RTTI if possible. Is there another way?

Answer 1

So, you want to return an iterator by value, but have its dynamic type vary depending on the override of begin/end you called? No problem - just add another layer of indirection.

class Base {
public:
  class Iterator {
  public:
    struct Impl {
      virtual ~Impl() {}
      virtual CollectionObjectBase& operator*() = 0;
      virtual void operator++() = 0;
      virtual bool operator==(Iterator::Impl const &other) const = 0;
    };
    Iterator() {}
    explicit Iterator(std::unique_ptr<Impl> &&i) : impl_(std::move(i)) {}
    Iterator(Iterator &&other) = default;

    CollectionObjectBase& operator*() { return **impl_; }
    Iterator& operator++() { ++*impl_; return *this; }
    bool operator==(Iterator const &other) const {
      return (!impl_ && !other.impl_) || (*impl_ == *other.impl_);
    }
  private:
    std::unique_ptr<Impl> impl_;
  };
  // ...

This uses the pointer-to-impl (pimpl) idiom to give each concrete subclass of Base its own concrete subclass of Base::Iterator::Impl, but still let you pass Base::Iterator objects around by value using move semantics to transfer ownership of the dynamic object.

NB. I made two default-constructed (nullptr) iterators compare equal so you don't need to create a real instance for end.