C++ -& CRTP . Type erasure vs polymorphism

Question

OK here we go. I'm trying to use the CRTP template in order to remove the need of polymorphism from my app. I use an aproach like the one bellow

template <RealType> class Base 
{

    void doSomething()
    {
         static_cast<RealType>(this)->doSomethingImpl()
    }

class Derived1 : public Base
{
    void doSomethingImpl()
    {
        /* do something, for real */
    }
}

class Derived2 : public Base
{
    void doSomethingImpl()
    {
        /* do something else */
    }
}

This aproach, if I understood correctly, allows my classes to have no vtable, so function calls are direct and don't require the extra indirection.

Now imagine I want to store all my Derived# classes in a container. Let's say a vector.

First approach : I can create a non-template SuperBase class from which Base inherits and store that in the container.

However it seems to me that if I want to do that, I will have to make doSomething virtual, in SuperBase. And my goal is mainly not to have a vtable.

Second approach : I use type erasure, i.e. something like boost::any to store my elements in the Vector. But then, I don't see a way I can iterate over the elements and call doSomething on them, because to "use" boost::any, I need to know the real type of the object when iterating.

Do you think what I want to do is even possible ?

Seems to me that it is because doSomething() is part of Base but except using inheritance, I can't see a way to do it ....

Answer 1

You can combine both strengths.

#include <iostream>

struct AnimalBase
{
    virtual std::string speak() const = 0;
    virtual ~AnimalBase() {};
};

template <typename Derived>
struct Animal : AnimalBase
{
    std::string speak() const
    {
        return static_cast<const Derived*>(this)->speak();
    }
};

struct Dog : Animal<Dog>
{
    std::string speak() const
    {
        return "Woof! Woof!";
    }
};

struct Cat : Animal<Cat>
{
    std::string speak() const
    {
        return "Meow. Meow.";
    }
};

int main()
{
    AnimalBase* pets[] = { new Dog, new Cat };

    std::cout << Dog().speak() << '\n'
              << Cat().speak() << '\n'
              << pets[0]->speak() << '\n'
              << pets[1]->speak() << std::endl;

    delete pets[0];
    delete pets[1];
    return 0;
}

Answer 2

And my goal is mainly not to have a vtable.

If you want this, then, unless you implement your own virtual dispatch system (which would likely be inferior to what the compiler does), you're stuck with templates, a.k.a. compile-time polymorphism. And as the name says, in order to use this, everything must be known at compile-time. If you need to make decisions based on runtime events (like, e.g., user input), you want runtime polymorphism.

I can't help but have to ask: Why do you want to avoid vtables? (And if you're so determined, why aren't you programming in C?)

Answer 3

You can do what you want with the proper theoretical operation which is NOT polymorphism, but unification. Most people have no idea what a sum type (discriminated union) is and what it is for which is why they consistently abuse inheritance, which is entirely unrelated.

Unions are more popular in C, for example X-Windows event messages are union based, because they're broken in C++.

A union is the correct way to represent heterogeneous data types as a single type, hence the name unification: it unifies all the components into a single type. Unions always have a finite known number of components, functions using unions invariably use a switch on the discriminant to select the right handler code.

OOP cannot provide unification: it provides subtyping.

Templates provide something quite different again: parametric polymorphism.

All three concepts are quite distinct in both theory and practice. Subtyping OOP style turns out to be the least useful because what it can represent is heavily restricted, however those restrictions do permit dynamic dispatch to an open set of subtypes, which is very nice if it applies to your problem.

So now it is clear, in your array, all you need to put is a union of all your classes, and your problem goes away.

Only .. the classes have to be POD types in C++ at present due to an unprincipled restriction. So the best solution is to use a union of raw C functions, since C function pointers are PODs.

Something like:

enum tag {tag_X, tag_Y};

struct X { int x; };
void px(X a) { cout << a.x; }
struct PX { tag t; X a; void (*p)(X); };

struct Y { double x; };
void py(Y a) { cout << a.x; };
struct PY {tag t; Y a; void (*p)(Y); };

union XY { PX anX; PY anY; };

PX x1 = { tag_X, { 1 }, px };
PY y1 = { tag_Y, { 1.0 }, py };

XY xy1.anPX = x1;
XY xy2.anPy = x2;

XY xys[2] = {xy1, xy1};

xy = xys[0];
switch (xy.anPX.tag) { // hack
  case tag_X: xy.anPX.p (xy.PX.x); break;
  case tag_Y: xy.anPY.p (xy.PY.x); break;
}

If you think this is ugly, you're right: C and C++ are brain dead. Another solution is to use a tag and a pointer which is cast to a void*, then use the tag to cast to the required type: this is much easier but requires heap allocation of the data and hence you have a memory management issue. Another alternative is Boost variant type (which automates some of the housekeeping but is still very ugly).

Here's similar code in Ocaml:

type xy = X of int | Y of double
let print u =
  match u with 
  | X x -> print_int x 
  | Y x -> print_double x
in 
  print (X 1);
  print (Y 2.0)

In this code the X and Y are the tags of the C code above, they're called type constructors because they construct an xy type out of an int or a double (resp.). The match expression there is just a switch with automatic selection of the right component type and scoping used to ensure you can't refer to the wrong component (as you could in the C code), also there's no break, match handlers don't drop thru, and the memory management is done by a garbage collector.