Sorush Khajepor

Researcher & Developer
Twitter_Logo_Blue

How to use type erasure pattern to decouple polymorphic classes in C++?

Introduction

Type erasure pattern mean writing a behaviour (or function) that works with various types.

Highlights of the post:

  • classic polymorphism for one class family (Shape) is explained with an example.
  • Using duck-typing of templates, member funtion of unrelated classes can be called in an external function.
  • A vector of unrelated classes can be created with wrapper classes made by templates.
  • A dependency injection by polymorphism is explained with an example.
  • The dynamic dispatch goes through two pointer indirection when a class and its operations/strategies are loosely coupled.
  • The example is recreated using templates where a class and its operations/strategies are completely decoupled. The code is much tidier and smaller.
  • It is shown that for any number of types to work together just one pointer indirection is necessary when templates are employed.

Old-school Polymorphism

In classic object-oriented programming, the polymorphism usually leads to a kind of type earsure. See this exmaple:

struct Shape{
    virtual double getVolume()=0;
};

struct Sphere: Shape{
    double radius;
    Sphere(double r):radius(r){}
    double getVolume() override{ return 4.19*radius*radius*radius;}
};

struct Box: Shape{
    double side;
    Box(double s):side(s){}
    double getVolume() override {return side*side*side;}
};

double ComputeMass(Shape& shape){
    return shape.getVolume()*1000;
}

This can be employed in the below program:

using namespace std;
int main()
{
    Sphere sphere{1};
    Box box{1};

    cout<<ComputeMass(sphere); // 4190
    cout<<ComputeMass(box); // 1000
    
    // different types in a vector
    vector<Shape*> shapes{&sphere, &box};
    for (auto& s: shapes)
        cout<<ComputeMass(*s);
    return 0;
}

ComputeMass() function doesn’t have clue about Box or Sphere, and yet it calls correctly the right behavior of each derived shape. This magic of polymorphism is a kind of type-erasure.

This magic works because, both Box and Sphere inherit Shape interface. Their objects contain a virtual table (vtable) pointing to their implementation of virtual functions. In ComputeMass(shape&) Box or Sphere objects are passed as Shape, but their vtable still preserved which points to the correct functions. Since this dipatch is done by pointers, it can happen during runtime, therefore, this is also called dynamic dispatch.

Dynamic dispatch has some teeny tiny costs:

  • objects contain a pointer pointing to their vtable,
  • there is an indirection to the vtable to run a virtual function,
  • if compiler doesn’t know which function will be called at runtime, it won’t optimise the function in relation to the cantext it is called.

Template replacing polymorphism

Thanks to templates we can have “duck typing” in C++, and for the previous example the interface can be removed:

struct Sphere{
    double radius;
    Sphere(double r):radius(r){}
    double getVolume() { return 4.19*radius*radius*radius;}
};

struct Box{
    double side;
    Box(double s):side(s){}
    double getVolume() {return side*side*side;}
};

double ComputeMass(const auto& shape){
    return shape.getVolume()*1000;
}

And use it like this:

Sphere sphere{1};
Box box{1};
auto m1 =ComputeMass(sphere);
auto m2 =ComputeMass(box);

Any object that has getVolume() function can be called in ComputeMass(). The compiler behind the scene, creates two function overloads ComputeMass(const Box&), ComputeMass(const Sphere&) to handle the direct calls. There is not a vtable or indirection of pointers, this is called static dispatch.

Vector of non-family objects

There is a catch in the previous example, we cannot have a vector made of different type objects without shared interface:

// not possible
std::vector<?> {box1, sphere1, box2, sphere2}

Well not completely true, it is possible to create such a vector with std::any but let’s not shoot ourself in the foot. So in this situations, old faithful interface is again the way to go. But imagine a scenario that you are not allowed to change Box and Sphere class to inherit from the same interface. How do create that vector? the answer is wrapper classes that share the same interface (decorator design pattern):

struct Sphere{ /*see previous example*/ };
struct Box{/*see previous example*/  };

struct Shape{
    virtual double getVolume()=0;
};

struct SphereWrapper: Shape{
    Sphere sphere;
    SphereWrapper(const Sphere& s):sphere(s){}
    double getVolume() override{ return sphere.getVolume();}
};

struct BoxWrapper: Shape{
    Box box;
    BoxWrapper(const Box& b):box(b){}
    double getVolume() override{return box.getVolume();}
};

int main(){
  auto b =  BoxWrapper{Box{1}};
  auto s = SphereWrapper{Sphere{1}};
  auto v = std::vector<Shape*>{&b,&s};
  for (auto& s:v)
    std::cout<<s->getVolume();
    return 0;
}

Here I stored the objects in the wrapper. However, if some other sections of the program work with Box and Sphere objects, the objects needs to live outside of the wrappers, thus we would store a pointer to objects in the wrappers.

OK, the goal is acheived all the objects added to a vector. But if we have many more classes to wrap like Sphere, Box, Cone, Cylinder, … do we have to write wrappers for all of them? Well No, looking at the wrapper classes, we notice they look very similar, we can make the compiler to make these classes for us:

struct Shape{
    virtual double getVolume()=0;
};

template<typename T>
struct ShapeWrapper: Shape{
    T shape;
    ShapeWrapper(const T& s):shape(s){}
    double getVolume() override{ return shape.getVolume();}
};

It can be used as:

int main(){
  auto b =  ShapeWrapper{Box{1}};
  auto s = ShapeWrapper{Sphere{1}};
  auto v = std::vector<Shape*>{&b,&s};
  for (auto& s:v)
    std::cout<<s->getVolume();
    return 0;
}

Notice how nicely, Shape and ShapeWarpper have no clue of Box, Sphere, Cone, so forth. Any object that has getVolume() function fits in them, and this is a type erasure or duck typing.

Dependency injection for decoupling

Dependency injection is a popular technique to decouple classes from operations. Let’s see if we can use previous type erasure ideas for it. Imagine we have a 3D printer that creates different shapes. The 3D printer can print them in linear or cirucal motion. So we have these classes and operations:

Classes: Box, sphere,...
Operations: printing motions: linear, circular, ...

Class  ->      Operation
Box    -> printed in linear motion
Box    -> printed in circular motion
Sphere -> printed in linear motion
Sphere -> printed in circular motion

2 classes x 2 operations = 4 combinations

There will be more combinations if we have more classes or operations.

Let’s program it. The shapes are one class family and the way they are printed are a different class family. We can create interfaces for the operations and add them to shape classes:

class Box;
struct BoxPrinter{
    virtual void print(Box&)=0;
};

class Sphere;
struct SpherePrinter{
    virtual void print(Sphere&)=0;
};

struct Shape{
    virtual void print()=0;
};

struct Sphere: Shape{
    double radius;
    SpherePrinter* printer;
    Sphere(double r, SpherePrinter* p):radius(r), printer(p){}
    void print()override{ printer->print(*this);}
};

struct Box: Shape{
    double side;
    BoxPrinter* printer;
    Box(double s, BoxPrinter* p):side(s), printer(p) {}
    void print() override{ printer->print(*this);}
};

Now we can write 4 special operations (strategies) for the printer to print different shapes:

struct  CircularMotionSpherePrinter: SpherePrinter{
    void print(Sphere& sphere) override{std::cout<<"printing sphere, circular motion...";};
};
struct  LinearMotionSpherePrinter: SpherePrinter{
    void print(Sphere& sphere) override{std::cout<<"printing sphere, linear motion...";};
};
struct CircularMotionBoxPrinter: BoxPrinter{
    void print(Box& sphere) override{std::cout<<"printing box, circular motion...";};
};
struct LinearMotionBoxPrinter: BoxPrinter{
    void print(Box& sphere) override{std::cout<<"printing box, linear motion...";};
};

The example can be used as:

int main()
{
    // opeartions or strategies
    CircularMotionSpherePrinter cs;
    LinearMotionSpherePrinter ls;
    CircularMotionBoxPrinter cb;
    LinearMotionBoxPrinter lb;
    
    // inject strategies
    Sphere sphere1{1, &cs};
    Sphere sphere2{1, &ls};
    Box box1{1, &cb};
    Box box2{1, &lb};
    
    // The library can print any defined shape
    std::vector<Shape*> vec{&box1, &sphere1, &sphere2, &box2};
    for (auto& shape: vec)
        shape->print();

    return 0;   
}

With the aid of dependency injection, we loosely decoupled shapes from printing operations. This technique is also called strategy desing pattern. In our example, different printing operations are different strategies.

Some notes:

  • Shape derived classes need to know about printing, but not the details. That’s why I said shapes and operations are loosely coupled.
  • There are 2 pointer indirections to call the right function:
shape.print() -> Box.print()/Sphere.print() 
printer.print() -> CircularMotionSpherePrinter/LinearMot...
  • For different operations, like visualize or serialize, we need to polute Box, Sphere classes agin and write the hierachy of poymorphic strategies.

Template for decoupling

Let’s write the previous example using the templates (I got ideas from Klaus Iglberger’s talk, see the references.):

struct Sphere{double radius;};

struct Box{double side;};

struct PrinterInterface{
    void virtual print()=0;
};

template<typename T, typename S>
struct PrinterModel: PrinterInterface{
    T object;
    S strategy;
    PrinterModel(T object_, S strategy_):object(object_), strategy(strategy_){}
    void print() override{
         Print(object, strategy);
    }
};

auto Print(const Box& box, const auto& strategy){
    std::cout<<"box is Printed. \n";
}
auto Print(const Sphere& sphere, const auto& strategy ){
    std::cout<<"sphere is Printed. \n";
}

struct LinearPrinting{};
struct CircularPrintingBox{};
struct CircularPrintingSphere{};

That’s it, now you can test it with this program:

int main(){
    Sphere s{1};
    Box b{2} ;
    auto sphereModel = PrinterModel{s,LinearPrinting{}};
    auto boxModel = PrinterModel{b, CircularPrintingBox{}};
    std::vector<PrinterInterface*> printerModels{&sphereModel, &boxModel};

    for (auto& model: printerModels)
        model->print();
    return 0;
}

Some points:

  • Box and Sphere don’t know they will be printed, we have complete decoupling.

  • Strategies can be anything, they are not bound by an interface.

  • If desired, Box and Sphere can use the same strategy.

  • If a new shape class like Cone is added, we just need to add one function, Print(const Cone&,...). We may be able to use previousely defined strategies, otherwise we easily write a new strategy.

  • We wrote much less code.

  • PrinterModel is a class template that is instantiated by the compiler for different combination of shapes and operations. Compiler writes for us.

  • If we need to limit types that are accepted in PrinterModel or Print functions, C++20 Concepts can be easily employed.

  • We have only 1 pointer indirection:

model->print()  --->   
        PrinterModel<Box, CircularPrintingBox> or 
        PrinterModel<Sphere, LinearPrinting> or ...

This indirection is necessary to have the sweet dynamic (runtime) dispatch.

Finally, all the classes can be swept into one class of Printer:

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

struct Sphere{};
struct Box{};

struct Printer{
    struct PrinterInterface{
        virtual ~PrinterInterface(){};
        void virtual print()=0;
    };

    template<typename T, typename S>
    struct PrinterModel: PrinterInterface{
        T object;
        S strategy;

        PrinterModel(const T& object_, const S& strategy_):object(object_), strategy(strategy_){}
        void print() override{
            Print(object, strategy);
        }
    };

    std::unique_ptr<PrinterInterface> model;
    
    void print(){model->print();}

    Printer(Printer&& other){
            model = std::move(other.model);
    }
    
    template<typename T, typename S>
    Printer(const T& object_, const S& strategy_): 
        model(new PrinterModel<T,S>{object_, strategy_}){}
};

auto Print(const Box& box, const auto& strategy){
    std::cout<<"box is Printd. \n";
}
auto Print(const Sphere& sphere, const auto& strategy ){
    std::cout<<"sphere is Printd. \n";
}

struct LinearPrinting{};

int main(){

    Sphere s{};
    Box b{};
    std::vector<Printer> printers;
    printers.push_back(Printer{s,LinearPrinting{}});
    printers.push_back(Printer{b, CircularPrintingBox{}});

    for (auto& model: printers)
        model.print();
        
return 0;}

Templates for decoupling multiple types

The idea of having model class to create multipe combinations of two types can be extended to three types:

template<typename T1, typename T2, typename S >
struct PrinterModel: PrinterInterface{
    T1 object1;
    T2 object2;
    S strategy;
    PrinterModel(T1 object1_, T2 object2_, S strategy_):object1(object1_),object2(object2_), strategy(strategy_){}
    void print() override{
         Print(object1, object2, strategy);
    }
};

Using variadic template and fold-expression, the dynamic dispatch can happen for combination of many types with only one redirection of pointer:

#include<vector>
#include<iostream>
#include<tuple>
struct PrinterInterface{
    void virtual print()=0;
};

template<typename S, typename ...T>
struct PrinterModel: PrinterInterface{
    std::tuple<T...> objects;
    S strategy;
    PrinterModel( S strategy_, T... objects_):
            objects(std::make_tuple(objects_...)),
            strategy(strategy_){}
    
    template<std::size_t... I>
    void print_tuple(std::index_sequence<I...>){
        Print(std::get<I>(objects)...,strategy);
    }

    void print() override{
        static constexpr auto Indices = std::make_index_sequence<sizeof...(T)>();
        print_tuple(Indices);
    }
};

struct Sphere{};
struct Box{};
struct Cone{};
struct LinearPrinting{};

auto Print(const Sphere& sphere, const auto& strategy ){
    std::cout<<"sphere is Printed. \n";
}
auto Print(const Sphere& sphere, const Box& box, const auto& strategy){
    std::cout<<"Sphere box is Printed. \n";
}
auto Print(const Sphere& sphere, const Box& box, const Cone& cone, const auto& strategy){
    std::cout<<"Sphere box cone is Printed. \n";
}

int main(){
    Sphere s{};
    Box b{} ;
    Cone c{};
    auto sphereModel = PrinterModel{LinearPrinting{},s};
    auto sphereBoxModel = PrinterModel{LinearPrinting{},s,b};
    auto sphereBoxConeModel = PrinterModel{LinearPrinting{},s,b,c};
    std::vector<PrinterInterface*> 
        printerModels{&sphereModel, &sphereBoxModel, &sphereBoxConeModel};

    for (auto& model: printerModels)
        model->print();
return 0;
}

When to use

Imagine we have a relationship of one class to many operations like

Sphere -> Serialize_json, Serialize_xml, Serialize_...

and the relations ends there, for example serialize_json won’t be extended more. Therefore, there is only one pointer redirection. I think the type-erasure discussed here is overkill; the old-faithful dynamic polymorphism is the way to go, it’s more readable, compiler creates less assembly code, and it’s way easy to maintain. So Serialization will be a member of sphere. Of course, this is subjective to many other considerations.

If we have the relationship of many classes to many operations like

Sphere, Box, Cone, … -> serialize_json, serialize_xml, serialize…

with the type erasure technique discussed in this post we can group operations like

operation<Sphere,Serialize_json>, operation<sphere,Serialize_xml>,
operation<Box,Serialize_json>, operation<Box, Serialize_xml>,
operation<Cone,Serialize_json>, operation<Cone, Serialize_xml>,...

where each opertion can be refered with one interaface pointer, Serialization*. Of course, this depends on what is your criteria for readabilty and maintainance of the code. You may be well comfortable with dependency injection and this idea can add no value to your code, so YAGNI. Or this pattern may make the expensive part of your code run faster and more maintainable.

References

In this post, I used many ideas of the great talk of Klaus Iglberger at CppCon 2021.

Subscribe

I notify you of my new posts

Latest Posts

Comments

0 comment