An example of template subclassing

Question

I was reading SEQAN documentation. In Getting Started section, they mentioned "Template Subclassing" as a method to overcome runtime polymorphism overhead.

OOP vs. Generic Programming: In SeqAn, we use a technique called template subclassing which is based on generic programming. This technique provides polymorphism into C++ programs at compile time using templates. Such static polymorphism is different from runtime polymorphism which is supported in C++ using subclassing and virtual functions. It comes at the cost of some additional typing but has the advantage that the compiler can inline all function calls and thus achieve better performance. An example will be given in the section “From OOP to SeqAn” in the First Steps Tutorial.

Unfortunately there is no example to illustrate its usage yet. I really appreciate if anyone provide a simple example.

I wrote simple template class but I am not sure if this what they meant by template subclassing!

struct Base {
    virtual void nockNock() {
        std::cout << "I am Base class." << std::endl;
    }
};


template<typename T>
class Derived: public Base {
public:

    void anotherNock() {
        std::cout << "It's me the Derived class." << std::endl;
    }
    void nockNock() {
        std::cout << "I am Derived class." << std::endl;
        anotherNock();
    }

public:
    Derived(){};
};



int main() {
    Base* myArray[10];

    myArray[0] = new Derived<int>;

    myArray[0]->nockNock();

    return 0;
}

Answer 1

There’s an existing question/answer that describes what template subclassing means, and how it’s used in SeqAn. Let me give a simpler example here.

// No default `Spec` given = “virtual” base class!
template <typename Spec> struct Fruit {};

template <typename Spec>
inline void eat(Fruit<Spec> const&) {
    std::cout << "nibbling an unknown fruit\n";
}

Note that methods in template subclassing are always free functions, since method dispatch works strictly via overloading, not overriding, as in conventional subclassing.

This defines a base class for Fruits, and one method, eat, which can be called on any fruit.

We will now define a hierarchy of specialisations (“subclasses”). First, simple ones; these are simply type tags, which will be plugged into the Spec template argument:

struct Orange;
struct Apple;

That’s it. We don’t even need to define these tags in our example, declaring them is enough (but for more complex cases definitions may become necessary; in SeqAn, type tags are always defined).

Now, here’s an override of the eat method for Apples:

template <>
inline void eat(Fruit<Apple> const&) {
    std::cout << "scrunching an apple\n";
}

Since we don’t override the method for Oranges, those will always call the base class method.

Here are some more specialisations, for citrus fruits (a subclass hierarchy):

struct Lemon;
struct Lime;
template <typename Spec = Lemon> struct Citrus { };

Note that, unlike for Apples and Oranges, Citrus is itself a template that can be subclassed. We could now override eat for Citrus fruits the same as before, but I want to show how a subclass method can dispatch to a base class method; to do this, let’s introduce a helper function template eat_citrus, which will be called from eat:

template <typename Spec>
inline void eat(Fruit<Citrus<Spec>> const&) {
    eat_citrus<Spec>();
}

Here’s the base class definition of eat_citrus for any Citrus:

template <typename Tag = Lemon>
inline void eat_citrus() {
    std::cout << "ew, that’s sour!\n";
}

And here’s the override for Limes:

template <>
inline void eat_citrus<Lime>() {
    std::cout << "nice taste, but ";
    eat_citrus<>(); // Calls the base class method.
}

Finally, if we use these classes as follows:

// Does not work, since `Fruit` is “virtual”:
// Fruit<> fruit;
Fruit<Orange> orange;
Fruit<Apple> apple;
Fruit<Citrus<>> lemon;
Fruit<Citrus<Lime>> lime;

eat(orange);
eat(apple);
eat(lemon);
eat(lime);

… we get this output:

nibbling an unknown fruit
scrunching an apple
ew, that’s sour!
nice taste, but ew, that’s sour!

Runnable code on Coliru

In SeqAn, the above is done slightly differently; I’ve changed it here for simplicity and, to be honest, because it’s been years since I’ve worked with SeqAn and I don’t remember the details. If I remember correctly, eat_citrus isn’t actually necessary and tag dispatch + overloading (as mentioned by Yuki) would be used here instead of template specialisation.

Also note that my code doesn’t use any actual inheritance in C++ parlance (i.e. Fruit<Apple> doesn’t inherit from Fruit<whatever>). This isn’t strictly necessary but often quite useful, and IIRC most SeqAn class templates do also actually inherit their base class.

Answer 2

After a brief look at SeqAn manual I came up with the following example:

namespace Tags {
struct Noone {};
struct Someone {};
}

template <typename T, typename U>
class Base {
public:
  using KindOfThing = U;

  // implement algorithm
  bool knock() {
    static_cast<T*>(this)->knockKnock();
    static_cast<T*>(this)->listen();
    static_cast<T*>(this)->knockKnock();
    static_cast<T*>(this)->tellName("Johnny");
    return static_cast<T*>(this)->knockKnock();
  }
};

template <typename T>
class Base<T, Tags::Noone> {
public:
  using KindOfThing = Tags::Noone;

  void work() {
    static_cast<T*>(this)->makeSounds();
    static_cast<T*>(this)->doJob();
  }
};

class WashingMachine : public Base<WashingMachine, Tags::Noone> {
public:
  void makeSounds(){};

  void doJob(){};
};

class Meow : public Base<Meow, Tags::Someone> {
public:
  Meow() : meows(0) {}

  //implement Base interface
  void listen() { std::cout << "..." << std::endl; }

  //implement Base interface
  bool knockKnock() {
    std::cout << "Meow..." << std::endl;
    return meows++ > 3;
  }

  void tellName(std::string const& name) { (void)name; }

  int meows;
};

class WhoIsThere : public Base<WhoIsThere, Tags::Someone> {
public:
  //implement Base interface
  void listen() { std::cout << "<Steps>..." << std::endl; }

  //implement Base interface
  bool knockKnock() {
    std::cout << "WhoIsThere?" << std::endl;
    return isDone;
  }

  void tellName(std::string const& name) {
    isDone = true;
    std::cout << name + " is here))!" << std::endl;
  }

  bool isDone;
};

template <typename T, typename U>
void performKnocking(T&& item, U) {
  std::cout << "......" << std::endl;
  while (!item.knock())
    ;
}

template <typename T>
void performKnocking(T&& item, Tags::Noone) {
  std::cout << "Noone" << std::endl;
}

template <typename... TArgs>
void performKnockingToEveryone(TArgs&&... sequence) {
  int dummy[] = {(performKnocking(sequence, typename TArgs::KindOfThing()), 0)...};
}

int main() {
  performKnockingToEveryone(
    Meow(), WashingMachine(), WhoIsThere(), Meow(), WashingMachine());
  return 0;
}

The point is that the design that SeqAn is telling is moving from the realm of usual OOP programming (with polymorphism, type abstractions and etc.) to C++ template programming (more precisely see Item 1 in Effective C++). The same like there are zellions of books on OOP design, not less, if not more, there are material on Template C++ programming (see The Definitive C++ Book Guide and List for both kinds of programming techniques and more).

In this example, I show two techniques of designing that the SeqAn documentation emphasizes.

• There is a base implementing some kind of operation that has several steps common for other subclasses. The base provide kind of Template Method (there is nothing related to C++ templates there, it is purely OOP pattern, just the name has the same word) from operations - setting an interface (not OOP interface, but C++ Template interface) for the deriving classes. Those subclasses, in their turn, implement those operations. You get static (resolved at compile time behaviour) polymorphism (type that has an interface that has different behavior from one instance to another). There is no runtime polymorphism because for runtime (OOP realm) those all are different types, they are all different for compile time as well. This polymorphism exists in C++ templates (templates parameters and templates declarations). Example: Boost Iterator Facade.

• Tag dispatching technique employs function overloading resolution depending on the argument(s) type(s). It helps when you have free function as part of your API and chose necessary one to call depending on situation (example STL Iterators iterator_tag(s) and iterator free functions). For exmaple, consider OOP Visitor Pattern and you have AbstractVisitor and KnockingVisitor. You take a vector of Base* and call accept on each, that calls visit and your KnockingVisitor does the knocking. With tag dispatching you use tags. This might be a lame comparation between OOP techniques and tag dispatching, but it is just one of many possible examples. Like with OOP design where and what pattern to use, with C++ Templates techniques you need experience.

This example is quite primitive, because there is no actual task behind it is design, however, when you have an ambitious goal that gets more interesting and complicated. C++ Templates might be one of the choices to archive it.