Iterate C++ list<derived> as base class

Question

What I want to do is this:

class Ba { }
class Da : public Ba {}
class Db : public Ba {}

class Bb // abstract base class that must not be a template.
{
    void Process()
    {
        list<Ba*>::iterator pos;
        // I known the derived class will also derive
        // from list<Dx*> where Dx derives from Ba
        for(pos = this->begin(); pos < this->end(); pos++)
            something(*pos);
    }
}

template<T> class L : public Bb , list<T*> // T is always derived from Ba
{
}

But that's invalid. So what's the next best thing?

An alternately formulation has a global Process get a passed a Bb pointer where the type is not know til run-time:

void GlobalProcess(Bb* bb) // don't know what kind of Bb (which L) got passed in.
{
        list<Ba*>::iterator pos;
        // I known the derived class will also derive
        // from list<Dx*> where Dx derives from Ba
        for(pos = bb->begin(); pos < bb->end(); pos++)
            something(*pos);
}

I have a few reasons for doing this but about half of it is feeling out the edges of the C++ system.

---

The simplest form of the problem I can come up with is that I need to iterate over a list<D*> from code where all the info I'm allowed to use at compile time is that D derives from B. This situation can arise from being passed a list<D> via a pointer to an abstract base class or where the code its self is in a base class.

This would all work just fine if only list<D*>::iterator were derived from list<B*>::iterator

Answer 1

First of all, don't inherit from std::list<>, the classes in the STL (with a few minor exceptions) are not meant to be derived from. They don't have virtual members, there is no benefit from doing so, it can only result in problems.

You question is a little vague and confusing. But assume you want to do this:

struct A {};
struct B : public A {};
std::list<B> l;

for(std::list<A>::iterator it = l.begin(); it != l.end(); ++it) {
    whatever(*it);
}

clearly this is invalid. But you can do something like this:

struct A {};
struct B : public A {};
std::list<B> l;


void whatever(A& a) {
    // do something with an A
}

std::list<B> l;
for(std::list<B>::iterator it = l.begin(); it != l.end(); ++it) {
    whatever(*it);
}

or better yet:

struct A {};
struct B : public A {};
std::list<B> l;

void whatever(A& a) {
    // do something with an A
}

std::for_each(l.begin(), l.end(), whatever);

EDIT:

To do what you want, you just need to do a little extra template work like this:

class Ba {};
class Da : public Ba {};
class Db : public Ba {};

template <class T>
class Bb {
    void Process() {
        list<T>::iterator pos;
        for(pos = begin(); pos < end(); pos++)
            something(*pos);
    }
}

template <class T>
class L : public Bb<T>, std::list<T> {
}

or you could make Process and interface like this:

template <class T>
class Bb {
public:
    virtual void Process() = 0;
}

template <class T>
class L : public Bb<T>, std::list<T> {
public:
    virtual void Process() {
        list<T>::iterator pos;
        for(pos = begin(); pos < end(); pos++)
            something(*pos);
    }
}

But it would be far better not to inherit from std::list<> as it will almost certainly lead to errors. Better to have std::list<T> be a member of the L class.

Answer 2

This should work by moving the processing code into the templated class:

class Bb
{
    virtual void Process() = 0;
}

template<T> class L : public Bb , list<T> // T is always derived from Ba
{
    virtual void Process()
    {
        list<T>::iterator pos;
        for(pos = begin(); pos < end(); pos++)
            something(*pos);
    }
}

This way you can specify the correct type of the iterator in Process() and still call it from a generic *Bb or &Bb.

Edit:

If you really don't want to use a virtual function and want to have all work done in class Bb, then Bb needs to know about the list<T> it should access. So it somehow needs to know about the type T and it won't be generic for different types T anymore.

If you have several different types T you will need to use polymorphism somewhere which will mean to use some virtual functions or templates.

Answer 3

If your iterating code is in the base class, then the list you are iterating over, must also be in the base class. This leads to the question, of what type of object the list should contain since you want to determine the type in the derived class. To solve this problem you can store shared pointers, effectively having a list, which can store polymorphic types. Here is the code:

#include <list>
#include <boost/shared_ptr.hpp>

class Ba { };
typedef boost::shared_ptr<Ba> BaSP;

class Da : public Ba {};
class Db : public Ba {};

void something(BaSP& a) {
    // do something with an Ba
}

class Bb // abstract base class that must not be a template.
{
protected:
    std::list<BaSP> list_;
    void Process()
    {
        std::list<BaSP>::iterator pos;
        for(pos = list_.begin(); pos != list_.end(); pos++)
             something(*pos);
    }
};

class L : public Bb 
{
    L() { 
        // the list can store Da and Db objects 
        boost::shared_ptr<Da> da;
        list_.push_back(da);
        boost::shared_ptr<Db> db;
        list_.push_back(db);
    }
};

This is the next best thing to the code you posted. If you give us the bigger picture of what you are trying to achieve, we might come up with a better design.

Answer 4

It is basically imposisble to get exactly what you want in C++. The language does not work this way, X : Y does not imply C<X> : C<Y> which is effectively the rule you want to apply. Why doesn't it? There are a few reasons:

• C may not be a container at all (there is no way to know).
• Template specialization (C<X> could have entirely different code than C<Y>).

• You open yourself up to problems like (pseudo code because this problem isn't exclusive to C++)

  class Base
  {
     void method();
  };
  
  
  class Child : public Base
  {
     void newmethod();
  };
  
  
  list<Base> base_list;
  list<Child> child_list;
  
  
   void safe(list<Base> list)
   {
      for(it in list)
      { it->method(); }
   }
  
  
   void still_safe(list<Child> list)
   {
      for(it in list)
      { it->newmethod(); }
   } 
  
  
   safe(base_list);
   safe(child_list);
   still_safe(child_list);
  
  
   void unsafe(list<Base> list)
   {
      list.push_back(new Base);
   }
  
  
   unsafe(base_list); // safe
   safe(base_list);
   unsafe(child_list); // maybe we get away with this
   still_safe(child_list); // KA BOOM! because the last item in child_list can't newmethod()
  

Note that you can do a more limited form of this (in a way that works and is safe) in some languages, but I can't think of any that will allow specifically what you are asking for. See also http://en.wikipedia.org/wiki/Covariance%5Fand%5Fcontravariance%5F%28computer%5Fscience%29

The real solution to this, in C++, for this sort of problem, is to make use of polymorphism (whether through templates parametrized on the list/iterator type or virtual methods that operate on C and D).