Polymorphic STL containers and iterators

Introduction

STL standard containers store objects of a fixed type, specified in their template parameter. They do not, therefore, support polymorphism by design: you can't store objects from a class hierarchy easily.

The first, naive idea is to define the container to store pointers to the base class:

typedef std::list<T*> polyTlist;

But this will pose two major problems:

1. Pointers will be copied as the container is being used, but the pointed objects (pointees) won't. This will cause memory leaks and multiple reference problems, for example:

   polyTList a;
   a.push_back(new T(1));
   polyTList b=a; // the pointer to T(1) is copied in b list
   
   *b.front()=T(2); // but *a.front() is also re-assigned!

2. Standard algorithms will work on the pointers, not on the pointees. Unless you want to sort objects by their address in memory, this isn't very useful...

Smart Pointers strike again!

Storing smart pointers in the container will partially solve the first problem. Ideally, we'd need smart pointers using either on the "deep copy" or "copy on write (cow)" ownership policy, as described in [1], to mimic the behavior of the standard containers. However, they require the base class to implement some kind of cloning method, which may have some impact on performance.

We prefer reference counted pointers such as [2], which mainly add automatic deallocation to standard pointer behavior. This ensures optimal performance in algorithms, and we will prevent accidents with multiple references through another mechanism, implemented in the iterators as described below:

typedef std::list<boost::shared_ptr<T> > polyTlist;
polyTList a;
a.push_back(new T(1));
polyTList b=a; // the pointer to T(1) is copied in b list

*b.front()=T(2); // should not compile

b.front()=new T(2); // correct way to re-assign

Polymorphic iterators

Accesses to data stored in containers is done through iterator objects. By defining our own iterators to support polymorphism transparently, standard algorithms can be applied to polymorphic containers without modification.

Let's first implement the const_iterator, which gives read-only access to the data. A first attempt could be:

template<class C, typename T>
class const_poly_iterator:public C::const_iterator
{
    typedef C::const_iterator _Parent;
    typedef const_poly_iterator<C,T> _Self;
public:
    _Self() {};
    _Self(const _Parent& p):_Parent(p) {};

    const T& operator*() const {return *_Parent::operator*();}
    const T* operator->() const {return &operator*();}
};

which basically overrides the dereferencing operators * and -> of the standard const_iterator of a given container C to perform a double dereferencing, giving access to the stored data.

However, there is a problem with certain implementation of the STL which use real pointers as iterators, especially for std::vector: C++ does not allow to derive a class from a built-in type, and the above template definition might therefore fail. We have to implement the const_iterator this way:

template<class C, typename T>
class const_poly_iterator
#if _MSC_VER>=1300 // VC7

  :public std::iterator_traits<typename C::const_iterator>
  // needed by VC7 (VS.NET / 2003) 

#endif
{
  typedef const_poly_iterator<C,T> _Self;
  //! mimic inheritage from the regular const_iterator

  //! because we cannot simply derive from it since

  //            some iterators are regular pointers

protected:
  typedef typename C::const_iterator I;
  //!< regular iterator of the underlying container

  I i; 
public:
  operator I&() {return i;}
  //!<needed to use poly_iterator in algorithms transparently

public:
  _Self() {};
  _Self(const I& p):i(p) {}

  const T& operator*() const {return **i;}
  T* const operator->() const {return &**i;}

public: // compatibility with I iterator

  _Self& operator++() {++i; return *this;}
  _Self& operator--() {--i; return *this;}
  bool operator==(const I& other) const {return i==other;}
  bool operator!=(const I& other) const {return i!=other;}
  bool operator==(const _Self& other) const {return i==other.i;}
  bool operator!=(const _Self& other) const {return i!=other.i;}
};

The implicit conversion operator "operator _Parent&()" mimics real inheritance of the C::const_iterator.

The const_iterator satisfies our requirement of safety about multiple references since it gives access to const data. Ideally, if we don't provide non-const iterators to polymorphic containers, we would be safe. However, many algorithms require iterators to exist for any container. Our solution is to define iterators with exactly the same interface as const_iterators:

template<class C, typename T>
  class poly_iterator:public const_poly_iterator<C,T>
#if _MSC_VER>=1300 // VC7 iterators must derive from iterator_traits

  ,public std::iterator_traits<typename C::iterator>
#endif
{
  typedef poly_iterator<C,T> _Self;
  typedef const_poly_iterator<C,T> _Parent;
  typedef typename C::iterator I;
  //!< regular iterator of the underlying container

 
  //! mimic inheritage from the regular iterator

  //! because we cannot simply derive from it since

  //            some iterators are regular pointers

public:
  operator I&() {return (I&)i;}
  //!<needed to use poly_iterator in algorithms transparently

public:
  _Self() {};
  _Self(const I& p):_Parent(p) {};
  _Self(const _Parent& p):_Parent(p) {};
  //!< construction form const_poly_iterator

public: // compatibility with I iterator

  _Self& operator++() {++i; return *this;}
  _Self& operator--() {--i; return *this;}
};

Here, the required implicit conversion operator poses a minor threat to the data safety as it gives access to the underlying smart pointer, which might be used in a dereferencing + assignment. However, as long as the polymorphic containers and iterators can be used transparently (i.e. the same way as standard containers) in a safe way, we consider that access to the underlying data structure can be allowed to users who "know what they are doing".

Enter the factory

To insert polymorphic objects in our structure, we need a way to clone them, i.e., a way to copy them while preserving their type. Since every class hierarchy might require a different way to clone its classes differently, we implement a generic class that wraps a class factory which will be used by default in the polymorphic container, but which can easily be overridden when needed:

template<typename T, typename R=boost::shared_ptr<T> >

struct poly_factory
{
    inline static R factory(const T& p) {return R(T::Factory(p));}
};

By default, the factory calls a method called "Factory" of the class hierarchy, which returns a smart pointer on a new copy of the object passed as parameter.

And now, the container(s)

Of course, we could implement a polymorphic_list, a polymorphic_vector, a polymorphic_queue, and so on, but laziness is the quality of the generic programmer, so we defined a single, template-based polymorphic_container that can derive from (almost) any standard container:

template<class C, typename T, typename F=poly_factory<T,C::value_type> >
class poly_container : public C
{
  typedef C _Parent;
  typedef poly_container<C,T,F> _Self;
  typedef typename C::value_type value_type; // (smart) pointer to T  

protected:
  typedef T& reference;
  typedef const T& const_reference;
public:
  typedef typename _Parent::size_type size_type;
  typedef poly_iterator<C,T> iterator;
  typedef const_poly_iterator<C,T> const_iterator;

  _Self() {}; // default constructor

  _Self(const _Parent& p):_Parent(p) {}; // copy constructor


  const_iterator begin() const {return _Parent::begin();}
  const_iterator end() const {return _Parent::end();}
  iterator begin() {return _Parent::begin();}
  iterator end() {return _Parent::end();}
  iterator insert(iterator i, const value_type& f) 
                   {return _Parent::insert(i, f);}
 
  void push_front(const value_type& f) {insert(begin(), f);}
  void push_back(const value_type& f) {insert(end(), f);}
  const_reference front() const {return *_Parent::front();}
  const_reference back() const {return *_Parent::back();}

  void push_front(const_iterator& f) 
    {copy(begin(), *_Parent::const_iterator(f));}
  void push_back(const_iterator& f) 
    {insert(end(), *_Parent::const_iterator(f));}

  iterator insert(iterator i, const T& f) 
    {return _Parent::insert(i, F::factory(f));}
  void push_front(const T& f) {insert(begin(), F::factory(f));}
  void push_back(const T& f) {insert(end(), F::factory(f));}
};

We added some methods to insert, push_back and push_front elements already present in other polymorphic containers, to avoid the need for a deep copy mechanism, as well as methods to insert directly objects through the use of the factory.

We can then define our example polymorphic list simply as:

typedef poly_container<std::list<boost::shared_ptr<T>,T> polyTlist;

Source code

The code is part of the "DYL" library available on SourceForge.

Future work

Our approach can be applied to associative containers such as std::map easily, the only reason why we didn't do it yet is because we don't need it in our application (laziness again).

References

1. Andrei Alexandrescu "Modern C++ Design, Generic Programming and Design Pattern Applied", 2001, Addison-Wesley In-Depth Series, ISBN 0-201-70431-5.
2. Smart pointers from Boost library.
3. Introduction to STL polymorphic containers.
4. An attempt to implement polymorphic-aware algorithms.