What's the cleanest implementation of this container of typed containers?

Question

I have different types, say A, B, C, that all inherit from some base class Base:

class Base { ... };
class A : public Base { ... };
class B : public Base { ... };
class C : public Base { ... };

I need a container, let's call it Master, that holds pointers to objects of types A, B and C. I want the Master container to provide an iterator over all contained Base objects, as well as specifically-typed iterators over all contained A, B and C objects. As a storage backend, I'll be using std::vector, but it would be nice if this can be switched easily later on.

Conceptually, this is the interface that Master should present to the outside world:

class Master {

  public:

    add(A *a);
    add(B *b);
    add(C *c);

    remove(Base *base);

    iterator<A*> a_begin();
    iterator<A*> a_end();
    iterator<B*> b_begin();
    iterator<B*> b_end();
    iterator<C*> c_begin();
    iterator<C*> c_end();
    iterator<Base*> base_begin();
    iterator<Base*> base_end();
    // also: reverse iterators, const iterators, reverse const iterators
};

The interface does not have to match this precise syntax. For example, someMaster.begin<A>() is perfectly fine too.

The trouble is, even in this simplified interface, you can already see some code duplication happening. It's much worse in the implementation. This is unacceptable, because I want to be able to extend the Master container easily later on, if I want to add classes D, E and F (also inheriting from Base). Preferably, I would like to extend it with just one or two lines of code.

All this could be implemented with lots of dynamic_casting, but that's ugly. I think some magic with templates and multiple inheritance could help me out here. What would be the cleanest implementation of this class?

Answer 1

Firstly you should look at Boost.Variant.
It allows you to store multiple unrelated objects in a container.
The iterator himself has to try to boost::get<T>() for his type to reach to the next object of type T.
If the object is not of type T, iterate forward.
If you want to iterate all objects, just return a variant of those objects, that way A, B and C don't have to be related to Base if you don't need them to or just a pointer to Base if all usecases will have a common base class.

Answer 2

Here's a sketch of what I would do:

// Beware, brain-compiled code ahead
template< typename T >
class typed_container
{
  typedef std::vector<T> data_t;
public:
  typedef data_t::iterator iterator;
  iterator begin() {return data_.begin();}
  iterator end  () {return data_.end();}
private:
  data_t data_;
};

typedef my_type_list<A,B,C> types_t;

class master : public derive_from< typed_container, types_t > {
  template< typename T >
  struct traits {
    typedef typename typed_container<T>::iterator iterator;
    iterator begin(typed_container<T>& c) {return c.begin();}
    iterator end  (typed_container<T>& c) {return c.end  ();}
  };
public:
  template< typename T > 
  typename traits<T>::iterator begin() {return traits<T>::begin(*this);}
  template< typename T > 
  typename traits<T>::iterator end  () {return traits<T>::end  (*this);}

  typedef my_assembling_iterator<types_t> iterator;

  iterator begin() {return my_assembling_iterator<types_t>.begin(*this);}
  iterator end  () {return my_assembling_iterator<types_t>.end  (*this);}
};

That leaves you to implement my_type_list (rather simple), derive_from (not as simple, but not too hard either), and my_assembling_iterator (I hadn't had a need to do something like that yet).

---

You can find a working C++03 type list implementation here. It only takes up to nine template arguments (but that's easily extended), and you'll have to write

typedef my_type_list<A,B,C>::result_t types_t

but it's simple and free and I know it works (because I'm using this library myself).

The derive_from template would look something like this:

//Beware, brain-compiled code ahead!
template< template<typename> class C, class  >
struct derive_from;

template< template<typename> class C >
struct derive_from< C, nil > {};

template< template<typename> class C, typename Head, typename Tail >
struct derive_from< C, my_type_list<Head,Tail> > : public C<Head>
                                                 , public derive_from<C,Tail> {};

That leaves the iterator. What are your needs regarding it? Does it have to be a random-access iterator (hard) or would a forward iterator suffice? Do you need any particular order to iterate over the elements?

Answer 3

I see at least two issues here:

How to avoid the 'redundancy' in the interface?

The master class has some functions which seem redundant (a_begin/a_end vs. b_begin/b_end vs. c_begin/c_end). My first suggestion is to use Java-style iterators in this case, so that you move the end functions out of the interface of master into the respective iterators.

Consider this example:

master *m = ..;
master::iterator<A*> a = m->getA():
while ( a->hasNext() ) {
    A *current = a->next();
    current->doSomething()
}

That way, you have just one iterator getter per concrete type (A, B, C).

I suspect that with some thinking, the iterator getter could maybe be a member template, so that you have just one get() template and be able to say m->get<A>(). For performance reasons, you'd specialize those getters to just iterate over specific containers (see below), I guess.

How to make the iterators iterate efficiently?

The Base iterator should iterate over all contained objects, the concrete iterators should only iterate over subsets of the contained objects. Do do this, I suggest to make master contain multiple std::vector objects, one per concrete type.

Your A iterator could then iterate over the vector containing all the A*, same for the other concrete types. The Base iterator would simply iterate over all containers, treating them as one continuous container.

Answer 4

Why not RTTI + boost filter_iterator ? People are usually afraid of RTTI but a filter_iterator with a template filter comparing two type_infos would be just fine.