PolicyAndTraits

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

 

 

Rainer D 6 P2 500x500Modernes C++ Mentoring

Be part of my mentoring programs:

  • "Fundamentals for C++ Professionals" (open)
  • "Design Patterns and Architectural Patterns with C++" (open)
  • "C++20: Get the Details" (open)
  • "Concurrency with Modern C++" (starts March 2024)
  • Do you want to stay informed: Subscribe.

     

    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 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.

    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 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).

    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 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.

     

     

     

     

     

    Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, 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, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, moon, Philipp Lenk, Hobsbawm, and Charles-Jianye Chen.

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

    My special thanks to Embarcadero
    My special thanks to PVS-Studio
    My special thanks to Tipi.build 
    My special thanks to Take Up Code
    My special thanks to SHAVEDYAKS

    Seminars

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

    Standard Seminars (English/German)

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

    • C++ – The Core Language
    • C++ – The Standard Library
    • C++ – Compact
    • C++11 and C++14
    • Concurrency with Modern C++
    • Design Pattern and Architectural Pattern with C++
    • Embedded Programming with Modern C++
    • Generic Programming (Templates) with C++
    • Clean Code with Modern C++
    • C++20

    Online Seminars (German)

    Contact Me

    Modernes C++ Mentoring,

     

     

    1 reply

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *