Templates, interfaces (multiple inheritance) and static functions (named constructors)

Question

Setup

I have a graph library where I am trying to decompose things as much as possible, and the cleanest way to describe it that I found is the following: there is a vanilla type node implementing only a list of edges:

class node
{
   public:
      int* edges;
      int edge_count;
};

Then, I would like to be able to add interfaces to this whole mix, like so:

template <class T>
class node_weight
{
   public:
      T weight;
};

template <class T>
class node_position
{
   public:
      T x;
      T y;
};

and so on. Then, the actual graph class comes in, which is templated on the actual type of node:

template <class node_T>
class graph
{
   protected:
      node_T* nodes;

   public:
      static graph cartesian(int n, int m)
      {
         graph r; 

         r.nodes = new node_T[n * m];

         return r;
      }
};

The twist is that it has named constructors which construct some special graphs, like a Cartesian lattice. In this case, I would like to be able to add some extra information into the graph, depending on what interfaces are implemented by node_T.

What would be the best way to accomplish this?

Possible solution

I thought of the following humble solution, through dynamic_cast<>:

template <class node_T, class weight_T, class position_T>
class graph
{
   protected:
      node_T* nodes;

   public:
      static graph cartesian(int n, int m)
      {
         graph r;

         r.nodes = new node_T[n * m];

         if (dynamic_cast<node_weight<weight_T>>(r.nodes[0]) != nullptr)
         {
            // do stuff knowing you can add weights
         }

         if (dynamic_cast<node_position<positionT>>(r.nodes[0]) != nullptr)
         {
            // do stuff knowing you can set position
         }

         return r;
      }
};

which would operate on node_T being the following:

template <class weight_T, class position_T>
class node_weight_position : 
      public node, public node_weight<weight_T>, public node_position<position_T>
{
    // ...
};

Questions

Is this -- philosophically -- the right way to go? I know people don't look nicely at multiple inheritance, though with "interfaces" like these it should all be fine.

There are unfortunately problems with this. From what I know at least, dynamic_cast<> involves quite a bit of run-time overhead. Hence, I run into a problem with what I had solved earlier: writing graph algorithms that require weights independently of whether the actual node_T class has weights or not. The solution with this 'interface' approach would be to write a function:

template <class node_T, class weight_T>
inline weight_T get_weight(node_T const & n)
{
   if (dynamic_cast<node_weight<weight_T>>(n) != nullptr)
   {
      return dynamic_cast<node_weight<weight_T>>(n).weight;
   }

   return T(1);
}

but the issue with it is that it works using run-time information (dynamic_cast), yet in principle I would like to decide it at compile-time and thus make the code more efficient.

If there is a different solution that would solve both problems, especially a cleaner and better one than what I have, I would love to hear about it!

Answer 1

What about type traits? If you have a compiler handy that supports parts of C++11 already, there is std::is_base_of in the <type_traits> header.

If you do not, there is boost with the same type trait.

Now, to really be able to use it, you need some meta programming:

// in the class...
//  branch on whether the node type has weights
static void set_weights(node_T* nodes, std::true_type){
    // has weights, set them
    // ...
}

static void set_weight(node_T* nodes, std::false_type){
    // doesn't have weights, do nothing
}

// in the function...
typedef std::is_base_of<node_weight<weight_T>, node_T>::type has_weights;
set_weight(nodes, has_weights());

This works thanks to some magic that lets the nested typedef type be either true_type or false_type based on whether the type trait is true or false. We need the meta programming (branching through overloads), because accessing members that aren't there will result in a compiler error, even if the access was in a branch that would never be executed.

I hope that makes any sense at all, it's quite difficult to type an answer to this topic on an iPod Touch...

Answer 2

First of all I am a big fan of multiple inheritance when used at the right time. So if it makes your design simpler then use it. As for getting rid of dynamic_cast<> and replacing it with a compile time selection that is easy. You just use overloaded functions to do the switching for you. You have one function which takes void* when you can't do anything useful with the type and a function that does something useful with the specified type. Your code would look like the following.

template <class node_T, class weight_T, class position_T>
class graph
{
protected:
    node_T* nodes;

private:
    static void do_stuff_with_weights(graph& r, void* /*dummy*/)
    {
    }

    static void do_stuff_with_weights(graph& r, node_weight<weight_T>* /*dummy*/)
    {
        // do stuff knowing you can add weights
    }

    static void do_stuff_with_pos(graph& r, void* /*dummy*/)
    {
    }

    static void do_stuff_with_pos(graph& r, node_position<position_T>* /*dummy*/)
    {
            // do stuff knowing you can set position
    }

public:
    static graph cartesian(int n, int m)
    {
        graph r;

        r.nodes = new node_T[n * m];

        do_stuff_with_weights(r, (node_T*) 0);
        do_stuff_with_pos(r, (node_T*) 0);

        return r;
    }
};