Interfaces and covariance problem

Question

I have a particular class that stores a piece of data, which implements an interface:

template<typename T>
class MyContainer : public Container<T> {
    class Something : public IInterface {
    public:
        // implement *, ->, and ++ here but how?
    private:
        T x;
    };

    // implement begin and end here, but how?

private:
    Something* data; // data holds the array of Somethings so that references to them can be returned from begin() and end() to items in this array so the interface will work, but this makes the problem described below
};

And I have an array of Somethings.

I have the need for Something to implement an interface class (IInterface in the example) which:

1. Contains pure virtual member functions which return something such that *retval returns a reference to the x member, retval-> returns the address of x, and ++retval makes retval refer to the next Something in the array.
2. The things that the pure virtual members return can be inherited from and returned by the implementation of the members
3. container[i] (where container is the array holding the Something objects) always returns something such that *retval always returns a reference to the same T for the same i.

Right now, the interface looks like this:

template<typename T>
class Container {
    class IInterface {
    public:
        virtual T& operator*() = 0;
        virtual T* operator->() = 0;
        virtual IInterface& operator++(); // this is the problem 
    };

    // returning a reference right now to support covariance, so subclasses can
    // derive from Container and then have a member class derive from IInterface
    // and override these to return their derived class, but this has a problem
    virtual IInterface& begin() = 0;
    virtual IInterface& end() = 0;
};

My current solution (have the virtual methods return an IInterface& and return a Something& in the implementation) has no problem with the requirements, except for the ++retval requirement. Because the Something is directly tied to the object it holds and can't point to a T with a pointer, there's no way that I can find to get ++ to make the variable refer to the next Something in the array.

If it helps to know, this is an iterator type system. I would have made it with the STL style iterators (where you just have an array of T) that are passed around by value and hold pointers to the values they represent, but that would break the interface because only references and pointers are covariant, and the objects already have to exist somewhere else already (in my code they're in the array) so you don't return a reference to a local object.

The purpose of this setup is so that one can write functions that take a Container& and iterate the container without knowing what type of container it is:

void iterate(Container<int>& somecontainer) {
    Container<int>::IIterator i = somecontainer.begin(); // right now this would return a reference, but it doesn't/can't work that way
    while (i != somecontainer.end()) {
         doSomething(*i);
         ++i; // this is the problem
    }
}

It's kind of difficult for me to describe, don't hesitate to let me know if you need more information.

Answer 1

What you are trying to do is called type erasure. Basically you want to provide a value type (which is the same across the whole inheritance hierarchy) that wraps the particular iterator type and offers a uniform dynamic interface.

Type erasure is usually implemented with a non-virtual class (the type erased) that stores a pointer to a virtual base class that implements the erasure, from which you derive different types that wrap each particular iterator. The static class would offer templated constructor/assignment operators that would dynamically instantiate an object of the derived type and store the pointer internally. Then you only need to implement the set of operations as dispatch to the internal object.

For the simplest form of type erasure possible, you can take a look at the implementation of boost::any (documentation is here)

Sketch:

namespace detail {
   template<typename T>
   struct any_iterator_base {
      virtual T* operator->() = 0;    // Correct implementation of operator-> is tough!
      virtual T& operator*() = 0;
      virtual any_iterator_base& operator++() = 0;
   };
   template <typename T, typename Iterator>
   class any_iterator_impl : any_iterator_base {
      Iterator it;
   public:
      any_iterator_impl( Iterator it ) : it(it) {}
      virtual T& operator*() {
         return *it;
      }
      any_iterator_impl& operator++() {
         ++it;
         return *this;
      }
   };
}
template <typename T>
class any_iterator {
   detail::any_iterator_base<T>* it;
public:
   template <typename Iterator>
   any_iterator( Iterator it ) : it( new detail::any_iterator_impl<T,Iterator>(it) ) {}
   ~any_iterator() {
      delete it;
   }
   // implement other constructors, including copy construction
   // implement assignment!!! (Rule of the Three)
   T& operator*() {
      return *it;   // virtual dispatch
   }
};

The actual implementation becomes really messy. You need to provide different versions of the iterator for the different iterator types in the standard, and the detail of the implementation of the operators might not be trivial either. In particular operator-> is applied iteratively until a raw pointer is obtained, and you want to make sure that your type erased behavior does not break that invariant or document how you break it (i.e. limitations on the type T that your adaptor can wrap)

For extended reading: - On the Tension Between Object-Oriented and Generic Programming in C++ - any_iterator: Implementing Erasure for C++ iterators - adobe any_iterator ,

Answer 2

I would suggest a look at the Visitor pattern.

Other than that, what you want is a value type that will be imbued with polymorphic behavior. There is a much simpler solution than James' using your IInterface.

class IInterface
{
  virtual ~IInterface() {}
  virtual void next() = 0;
  virtual void previous() = 0;
  virtual T* pointer() const = 0;

  virtual std::unique_ptr<IInterface> clone() const = 0;
};

std::unique_ptr<IInterface> clone(std::unique_ptr<IInterface> const& rhs) {
  if (!rhs) { return std::unique_ptr<IInterface>(); }
  return rhs->clone();
}

class Iterator
{
  friend class Container;
public:
  Iterator(): _impl() {}

  // Implement deep copy
  Iterator(Iterator const& rhs): _impl(clone(rhs._impl)) {}
  Iterator& operator=(Iterator rhs) { swap(*this, rhs); return *this; }

  friend void swap(Iterator& lhs, Iterator& rhs) {
    swap(lhs._impl, rhs._impl);
  }

  Iterator& operator++() { assert(_impl); _impl->next(); return *this; }
  Iterator& operator--() { assert(_impl); _impl->previous(); return *this; }
  Iterator operator++(int); // usual
  Iterator operator--(int); // usual

  T* operator->() const { assert(_impl); return _impl->pointer(); }
  T& operator*() const { assert(_impl); return *_impl->pointer(); }

private:
  Iterator(std::unique_ptr<IInterface> impl): _impl(impl) {}
  std::unique_ptr<IInterface> _impl;
};

And finally, the Container class will propose:

protected:
  virtual std::unique_ptr<IInterface> make_begin() = 0;
  virtual std::unique_ptr<IInterface> make_end() = 0;

And implement:

public:
  Iterator begin() { return Iterator(make_begin()); }
  Iteraotr end() { return Iterator(make_end()); }

Note:

You can do away with the std::unique_ptr if you can avoid the ownership issue. If you can restrict the IInterface to be behavioral only (by extracting the state into Iterator), then you can have the Strategy pattern kick-in, and use a pointer a statically allocated object. This way, you avoid dynamic allocation of memory.

Of course, it means your iterators won't be so rich, as it requires IInterface implementations to be stateless, and implementing "filtering" iterators, for example, would become impossible.