Type Erasure

Contents[Show]

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

PolicyAndTraits

First: What does type erasure mean?

  • Type Erasure: Type Erasure enables you to use 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.

typeErasureOO

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 programming, such as templates, you are not interested in interfaces; you are interested in behavior. Read more about the difference between interface-driven and behavior-driven design in my previous post, "Dynamic and Static Polymorphism".

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';

}

 

I use a dispatch table (line 1) that maps characters to callables in this example. 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.

callableAfter 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 method 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 (line7).

typeErasureOf 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

clang

GCC 11.2

gcc

 

MSVC 19.31

msvc

 

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

Pros and Cons

PolicyAndTraits

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 common base class, and 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 any 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.

 

 

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Louis St-Amour, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Neil Wang, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, and Wolfgang Fütterer.

 

Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, Ralf Abramowitsch, John Nebel, Mipko, and Alicja Kaminska.

 

 

My special thanks to Embarcadero CBUIDER STUDIO FINAL ICONS 1024 Small

 

My special thanks to PVS-Studio PVC Logo

 

Seminars

I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

Bookable (Online)

German

Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

New

Contact Me

Modernes C++,

RainerGrimmDunkelBlauSmall

 

 

 

Comments   

0 #1 FM 2022-04-12 07:42
The void pointer technique uses a function pointer which is simply as slow as OO. Generic Type erasure can be implemented without OO; you can carefully adjust the types and use void pointer instead. The benefits include embedded systems who switch OO polymorphism off. The concept encapsulates some function pointers, & the model decorates target functions to be fed to the concept. If model does not add instance data members, you can use concept by value rather than pointer, because it is no more abstract & model does not include extra data. Thus you can defeat both previous patterns.
https://stackoverflow.com/questions/51361606/stdany-without-rtti-how-does-it-work#51362647
Quote

Mentoring

English Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Interactive Course: The All-in-One Guide to C++20

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 587

Yesterday 4232

Week 587

Month 11516

All 10354823

Currently are 117 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments