Generic design mixed with curiously recurring temp

Question

Consider this kind of problem. I have a Base class and three classes derived from Base. For instance: DerivedA, DerivedB and DerivedC. Each derived class has its unique container. Hence DerivedA has std::vector<int>, DerivedB has std::set<int> and DerivedC has std::map<int, std::string>. And I want an interface in Base to access the container of derived class on which it is currently pointed to.

Base* d1 = new DerivedA;
for(std::vector<int>::iterator iter = d1->begin(); iter != d1->end(); ++iter)
{
     //processing
}

I tried to wrap each container to separate class and keep a pointer of their base in the Base class.

class CollA;

template<class T>
class traits;

template<>
class traits<CollA>
{
  public:
  typedef vector<int> container; 
};


template<class T>
class Coll
{
  public:
    typedef typename traits<T>::container container;
    typename container::iterator begin() const
    {
    }
};


class CollA : public Coll<CollA>
{
  typedef traits<CollA>::container container;
  public:
    container::iterator begin()
    {
      return V.begin();
    }
    private:
    vector<int> V;
};

class Base
{
  public:
    Base()
    {
    }
    // what to do here? I must keep a pointer to Coll; But Coll itself is a template
};

Suggest me something. I am kind of lost in this horrible design.

Answer 1

In order to do what you want, you need to define a common type of iterator that can be returned from the different begin() and end() overrides in the derived classes.

Before that, of course, you need to decide what exactly you want that iterator to do, as Yakk explained in his comment. For starters, you need to decide what value_type will result from indirecting through such an iterator. The only common type that I can think of given your three different containers is const int, as keys in std::maps are const and std::set iterators are const iterators (since the elements are keys themselves). So, when iterating using the common iterator type, you'll only be able to observe the ints in there.

Now, the iterator implementation will need to call different code (at runtime) depending on the derived class from which it originated. This is a typical use case for type erasure. When done properly, this would allow you to wrap any kind of iterator, as long as it supports the interface you need. In your case however, you may not need to go that far, since I suppose you know the full set of containers you need to support, so the set of iterator types is well known and bounded as well.

This means you can use a boost::variant to store the wrapped iterator. This should be more efficient than a full type erasure solution, since it avoids some internal virtual function calls and possibly some heap allocations (unless the type erasure solution can use some kind of small object optimization, which is fairly possible for iterators, but is even more complicated to implement).

Here's a skeleton implementation of such an iterator, together with the class hierarchy using it and some simple test code. Note that I've only implemented the basic iterator functionality that's needed to make your loop work.

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include "boost/variant.hpp"


//Helper function object types to implement each operator on the variant iterator.

struct indirection_visitor : boost::static_visitor<const int&>
{
   const int& operator()(std::vector<int>::iterator i) const { return *i; }
   const int& operator()(std::set<int>::iterator i) const { return *i; }
   const int& operator()(std::map<int, std::string>::iterator i) const { return i->first; }
};

struct prefix_increment_visitor : boost::static_visitor<>
{
   template<typename I> void operator()(I& i) const { ++i; }
};


//The iterator itself.
//It should probably hide the internal variant, in which case the non-member operators 
//should be declared as friends.

struct var_iterator : std::iterator<std::bidirectional_iterator_tag, const int>
{
   var_iterator() { }
   template<typename I> var_iterator(I i) : it(i) { }

   boost::variant<std::vector<int>::iterator, std::set<int>::iterator, std::map<int, std::string>::iterator> it;

   const int& operator*() { return boost::apply_visitor(indirection_visitor(), it); }

   var_iterator& operator++()
   {
      boost::apply_visitor(prefix_increment_visitor(), it);
      return *this;
   }
};

inline bool operator==(var_iterator i1, var_iterator i2) { return i1.it == i2.it; }
inline bool operator!=(var_iterator i1, var_iterator i2) { return !(i1 == i2); }


//Here's the class hierarchy.
//We use CRTP only to avoid copying and pasting the begin() and end() overrides for each derived class.

struct Base
{
   virtual var_iterator begin() = 0;
   virtual var_iterator end() = 0;
};

template<typename D> struct Base_container : Base
{
   var_iterator begin() override { return static_cast<D*>(this)->container.begin(); }
   var_iterator end() override { return static_cast<D*>(this)->container.end(); }
};

struct DerivedA : Base_container<DerivedA>
{
   std::vector<int> container;
};

struct DerivedB : Base_container<DerivedB>
{
   std::set<int> container;
};

struct DerivedC : Base_container<DerivedC>
{
   std::map<int, std::string> container;
};


//Quick test.

void f(Base* bp)
{
   for(auto iter = bp->begin(); iter != bp->end(); ++iter)
   {
      std::cout << *iter << ' ';
   }
   std::cout << '\n';

   //We have enough to make range-based for work too.
   for(auto i : *bp)
      std::cout << i << ' ';
   std::cout << '\n';
}

int main()
{
   DerivedA da;
   da.container = {1, 2, 3};
   f(&da);
   DerivedB db;
   db.container = {4, 5, 6};
   f(&db);
   DerivedC dc;
   dc.container = std::map<int, std::string>{{7, "seven"}, {8, "eight"}, {9, "nine"}};
   f(&dc);
}

Implementation notes:

• As mentioned above, this is not a complete bidirectional iterator; I chose that tag as the most powerful common iterator among your container types.
• I compiled and (superficially) tested the code in Clang 3.6.0 and GCC 5.1.0 in C++11 mode, and in Visual C++ 2013, using boost 1.58.0.
• The code works in C++14 mode as well in the compilers above (and also in Visual C++ 2015 CTP6), but needs a small change because of a bug in boost 1.58 (I'll have to report that), otherwise you'll get an ambiguity error. You need to remove the base class of indirection_visitor and let the return type of this visitor be determined automatically. This only works in C++14, as it uses decltype(auto) internally, and it's this new code that causes the ambiguity. Earlier versions of boost don't have this problem, but don't have autodetection of return types either.
• In C++14 mode and boost 1.58, you can use generic lambdas to implement simple visitors like prefix_increment_visitor, which makes the code more straightforward.
• I removed the comparison visitors from my first version of the code, as boost::variant already provides a default equality operator and it's enough for this case (the example is long enough as it is).
• You can add const in the required places to get true const iterator behaviour if needed (qualify begin() and end(), use static_cast<const D*> in CRTP, declare the variant to contain const_iterators, adjust the visitor).
• You can, of course, implement some sort of poor-man's variant and avoid using boost, but boost::variant makes everything much easier, cleaner and safer.