Type Erasure

Type erasure based on templates is a pretty sophisticated technique. It bridges dynamic polymorphism (object orientation) with static polymorphism (templates).

First: What does type erasure mean?

• Type Erasure: Type Erasure enables using various concrete types through a single generic interface.

You already quite often used type erasure in C++ or C. The C-ish type erasure is a void pointer; object orientation is the classical C++-ish way of type erasure. Let's start with a void pointer.

Void Pointer

Let's have a closer look at the declaration of std::qsort:

void qsort(void *ptr, std::size_t count, std::size_t size, cmp);

with:

int cmp(const void *a, const void *b);

The comparison function cmp should return a

• negative integer: the first argument is less than the second
• zero: both arguments are equal
• positive integer: the first argument is greater than the second

Thanks to the void pointer, std::qsort is generally applicable but also quite error-prone.

Maybe you want to sort a std::vector<int>, but you used a comparator for C-strings. The compiler can not catch this error because the necessary type information is missing. Consequentially, you end with undefined behavior.

In C++, we can do better:

Object Orientation

Here is a straightforward example, which serves as a starting point for further variation.

// typeErasureOO.cpp

#include <iostream>
#include <string>
#include <vector>

struct BaseClass{                                       // (2)
	virtual std::string getName() const = 0;
};

struct Bar: BaseClass{                                  // (4)
	std::string getName() const override {
	    return "Bar";
	}
};

struct Foo: BaseClass{                                  // (4)
	std::string getName() const override{
	    return "Foo";
	}
};

void printName(std::vector<const BaseClass*> vec){      // (3)
    for (auto v: vec) std::cout << v->getName() << '\n';
}


int main(){
	
	std::cout << '\n';
	
	Foo foo;
	Bar bar; 
	
	std::vector<const BaseClass*> vec{&foo, &bar};   // (1)
	
	printName(vec);
	
	std::cout << '\n';

}

std::vector<const Base*> (line 1) has a pointer to a constant BaseClass. BaseClass is an abstract base class used in line (3). Foo and Bar (line 4) are the concrete classes.

The output of the program is as expected.

To say it more formally. Foo and Bar implement the interface of the BaseClass and can, therefore, be used instead of BaseClass. This principle is called Liskov substitution principle and is type erasure in OO.

In object-orientated programming, you implement an interface. In generic programmings, such as templates, you are not interested in interfaces; you are interested in behavior. In my previous post, "Dynamic and Static Polymorphism", read more about the difference between interface-driven and behavior-driven design.

Type erasure with templates bridges the gap between dynamic polymorphism and static polymorphism.

Type Erasure

Let me start with a prominent example of type erasure: std::function. std::function is a polymorphic function wrapper. It can accept everything that behaves like a function. To be more precise. This everything can be any callable such as a function, a function object, a function object created by std::bind, or just a lambda expression.

// callable.cpp

#include <cmath>
#include <functional>
#include <iostream>
#include <map>

double add(double a, double b){
	return a + b;
}

struct Sub{
	double operator()(double a, double b){
		return a - b;
	}
};

double multThree(double a, double b, double c){
	return a * b * c;
}

int main(){
    
    using namespace std::placeholders;

    std::cout << '\n';

    std::map<const char , std::function<double(double, double)>> dispTable{  // (1)
        {'+', add },                                         // (2)
        {'-', Sub() },                                       // (3)
        {'*', std::bind(multThree, 1, _1, _2) },             // (4)
        {'/',[](double a, double b){ return a / b; }}};      // (5)

    std::cout << "3.5 + 4.5 = " << dispTable['+'](3.5, 4.5) << '\n';
    std::cout << "3.5 - 4.5 = " << dispTable['-'](3.5, 4.5) << '\n';
    std::cout << "3.5 * 4.5 = " << dispTable['*'](3.5, 4.5) << '\n';
    std::cout << "3.5 / 4.5 = " << dispTable['/'](3.5, 4.5) << '\n';
    std::cout << '\n';

}

In this example, I use a dispatch table (line 1) that maps characters to callables. A callable can be a function (line 1), a function object (lines 2 and 3), a function object created by std::bind (line 4), or a lambda expression (line 5). The key point of std::function is that it accepts all different function-like types and erases their types. std::function requires from its callable that it takes two double's and returns a double: std::function<double(double, double)>.

To complete the example, here is the output.

After this first introduction to type erasure, I want to implement the program typeErasureOO.cpp using type erasure based on templates.

// typeErasure.cpp

#include <iostream>
#include <memory>
#include <string>
#include <vector>

class Object {                                              // (2)
	 
public:
    template <typename T>                                   // (3)
    Object(T&& obj): object(std::make_shared<Model<T>>(std::forward<T>(obj))){}
      
    std::string getName() const {                           // (4)
        return object->getName(); 
    }
	
   struct Concept {                                         // (5)
       virtual ~Concept() {}
	   virtual std::string getName() const = 0;
   };

   template< typename T >                                   // (6)
   struct Model : Concept {
       Model(const T& t) : object(t) {}
	   std::string getName() const override {
		   return object.getName();
	   }
     private:
       T object;
   };

   std::shared_ptr<const Concept> object;
};


void printName(std::vector<Object> vec){                    // (7)
    for (auto v: vec) std::cout << v.getName() << '\n';
}

struct Bar{
    std::string getName() const {                           // (8)
        return "Bar";
    }
};

struct Foo{
    std::string getName() const {                           // (8)
        return "Foo";
    }
};

int main(){
	
    std::cout << '\n';
	
    std::vector<Object> vec{Object(Foo()), Object(Bar())};  // (1)
	
    printName(vec);
	
    std::cout << '\n';

}

Okay, what is happening here? Don't be irritated by the names Object, Concept, and Model. They are typically used for type erasure in the literature. So I stick with them.

std::vector uses instances (line 1) of type Object (line 2) and not pointers, such as in the first OO example. These instances can be created with arbitrary types because they have a generic constructor (line 3). Object has the member function getName (4) that directly forwards to the getName of object. object is of type std::shared_ptr<const Concept>. The member function getName of Concept is pure virtual (line 5). Therefore, the getName member function of Model (line 6) is used due to virtual dispatch. The getName member functions of Bar and Foo (line 8) are applied in the printName function (line 7).

Of course, this implementation is type-safe. So what happens in case of an error:

Error messages

Here is the incorrect implementation:

struct Bar{
    std::string get() const {                             // (1)
        return "Bar";
    }
};

struct Foo{
    std::string get_name() const {                        // (2)
        return "Foo";
    }
};

I renamed the method getName of Bar and Foo to get (line 1) and to get_name (line 2). 

Here are the error messages, copied with the Compiler Explorer.

All three compilers, g++, clang++, and MS compiler cl.exe, come directly to the point.

Clang 14.0.0

GCC 11.2

MSVC 19.31

What are the pros and cons of these three techniques for type erasure?

Pros and Cons

void Pointer

void Pointers are the C-ish way to provide one interface for different types. They give you complete flexibility. You don't need a base class; they are easy to implement. On the contrary, you lose all type information and, therefore, type safety.

Object Orientation

Object orientation is the C++-is way to provide one interface for different types. If you are accustomed to object-orientated programming, this is your typical way to design software systems. OO is challenging to implement but type-safe. It requires an interface and publicly derived implementations.

Type Erasure

Type erasure is a type-safe generic way to provide one interface for different types. The different types don't need a common base class and are unrelated.  Type erasure is pretty sophisticated to implement.

Performance

I ignored one point in my comparison: performance. Object orientation and type erasure are based on virtual inheritance. Consequentially, there is one pointer indirection happening at run time. Does this mean object orientation and type erasure is slower than the void Pointer? I'm not sure. You have to measure it in the concrete use case. When you use a void Pointer, you lose all type information. Therefore, the compiler can not make assumptions about the used types and generate optimized code. The performance questions can only be answered with a performance test.

What's Next?

I wrote almost 50 posts about templates in the last year. During that time, I learned a lot more about C++20. Therefore, I continue to write about C++20 and peek into the next C++ standard: C++23.