1 Type Erasure1.1 OverviewC++ is a strongly typed language, but when it comes to abstract design, the hard coding caused by strong typing can become a hassle. This is where we need the help of type erasure technology. Type erasure is a programming technique that allows you to operate on various concrete types through generic code that is independent of specific types, using only those specific types that conform to certain abstract behaviors, as if the other parts of these specific types have been erased here. There are two key points to type erasure: one is the abstraction of specific behaviors, and the other is the hiding of concrete types.
The advantage of type erasure is that it allows you to handle different types of objects using a unified interface, making the code more generic and flexible. Additionally, by encapsulating the implementation details of types, it avoids exposing too much type information in public interfaces, making the code cleaner and improving maintainability. Type erasure can also support polymorphism, allowing consistent code logic to handle them whether calling different types of interfaces or storing different types of objects.
Of course, the disadvantages of type erasure are also quite obvious. Type erasure generally requires some abstract type design, virtual functions, or pointers to encapsulate internal types, which often brings additional runtime overhead. After type erasure, the compiler cannot provide comprehensive type safety checks at runtime, and the code needs to perform real-time type checks to determine the actual type for correct processing. Other issues, such as the difficulty in debugging caused by hidden type information, also arise.
1.2 Application Scenarios
Type erasure can avoid exposing too many implementation details in interface design, allowing different types of objects to be handled through a unified interface, making the program more flexible in handling various types of data. Generally, when we encounter the following scenarios, we can consider using type erasure:
- The code expects a specific behavior (behavior similar to hard coding).
- The implementation of the code is based on the abstraction of this specific behavior, and many concrete types implement this behavior.
- The other parts of these concrete types, or parts unrelated to the specific behavior, need to be hidden.
The so-called erasure here means hiding or ignoring the parts of the specific type that are unrelated to the specific behavior. Designs using type erasure technology typically have the following characteristics:
- Generic code does not depend on the erased types (i.e., the unrelated parts of the types).
- In the (generic) code executing a specific behavior, the type is hidden.
- The code executing the specific behavior is called through a type-agnostic (independent of specific types) interface.
- The call point is the last place that knows the specific type (at this point, the type is abstracted).
- When it is necessary to use a non-specific behavior of a specific type, the type needs to be concretized (sometimes required).
The qsort() function in the C standard library is a typical example of a type-erased interface design:
qsort(void *base, size_t nmemb, size_t size, int (*compare)(const void *, const void *));The qsort() function’s sorting algorithm is independent of the specific data type; it uses void * to hide the specific type, remaining unaware of the specific type. Thus, in the qsort() function, the type is hidden. When we need to sort an array of integers, we only need to provide a comparison function for the integer type, like this:
int less_int(const void *lhs, const void *rhs) { return *(const int*)lhs - *(const int*)rhs; }int arr[8] = { 1, 8, 4, 7, 6, 2, 3, 9 };qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), less_int);As we can see, the place where the qsort() function is called is the last point that knows that the arr array is of type int. When it is necessary to know the specific behavior of int, for example, when the qsort() function needs to know the size relationship between two elements, it delegates this task to the compare() function, which requires knowledge of the specific type of the elements. Thus, the specific comparison function is provided by the caller of the qsort() function. The qsort() function certainly has many drawbacks; void * is already the bottom line of the C language, and we are more concerned with various implementations of type erasure technology in C++.2 Type Erasure Practice2.1 Object-Oriented “Interface + Implementation” We will demonstrate how to implement type erasure using the traditional “interface + implementation” approach with a very simple example, which is a typical example of object-oriented design:
class Shape {public: virtual void Draw(const Context& ctx) const = 0;};class Rectangle : public Shape {public: Rectangle(double w, double h) { ... } void Draw(const Context& ctx) const override { ... }};class Circle : public Shape {public: Circle(double r) { ... } void Draw(const Context& ctx) const override { ... } };void DrawShapes(const std::vector<Shape *>& shapes) { Context ctx{ ... }; for(const auto& shape : shapes) { shape->Draw(ctx); }}This design is a typical object-oriented inheritance system design idea. The DrawShapes() function does not need to care about the specific type of shape, and it seems that all actual types of shapes have been erased from the DrawShapes() function downwards. However, this does not count as good type erasure. First, drawing shapes is something that is inherently related to the graphical context environment; is it necessarily related to the shape object itself? The answer is no. Designing Draw() as part of the shape is a mistake, as it imposes an unnecessary dependency on the drawing context Context on all shapes. Secondly, if a neighbor has designed a very nice Triangle class that also supports drawing on the Context, I would like to use it, but I cannot because it is not a derived class of Shape. Thirdly, if we want to add persistence functionality to shapes, should we add a Serialize interface method in Shape? The impact of changing this interface is obvious. Finally, on the surface, it seems that the DrawShapes() function has no dependency on specific Circle or Rectangle types, but in reality, no part of this system can be reused independently; their dependencies have not been eliminated and still strongly depend on each other in a non-obvious way.In addition to design issues, traditional OO solutions have poor support for value semantics. In many cases, we are forced to use pointers or references to access objects. If a function needs to return an object that has undergone type erasure, it can only use pointers or references, but this is unsafe. If we use pass-by-value, it will lead to object slicing.2.2 Template-Based External Polymorphism2.2.1 Simple Template ImplementationModern practices of type erasure are mostly based on templates, which avoids the need for a common base class and cumbersome inheritance systems, and does not use virtual interfaces, so types will not have any dependency on virtual interfaces. The so-called external polymorphism means that types do not need to be specially designed based on a common base class, which brings flexibility to type reuse. A neighbor’s Triangle class can be used as long as it supports drawing on the Context.This section demonstrates how to use template mechanisms to replace the virtual interface mechanism from the previous section. First, the Circle and Rectangle classes no longer need a common base class, meaning that the shape objects have no relationship with each other, making them more independent and reusable. Additionally, from a design perspective, we will separate the Draw() function from Shape; this part is not our focus, so we can assume that each shape has been designed to draw itself on the drawing context Context:
class Rectangle {public: Rectangle(double w, double h) { ... }};class Circle {public: Circle(double r) { ... };}; // Drawing method based on Contextvoid DrawShape(const Context& ctx, Circle circle);void DrawShape(const Context& ctx, Rectangle rect);Based on the above, we can easily obtain such a function template:
template <typename ShapeT>void DrawSingleShape(const ShapeT& shape) { Context ctx{ ... }; DrawShape(ctx, shape);}It can be seen that through the DrawSingleShape() function, the specific types of Circle and Rectangle are erased, and the generic code within the DrawSingleShape() function supports function overloading like DrawShape() for each Shape. This assumption is what we refer to as a specific behavior. However, this solution has a significant problem: we cannot store graphic elements in a list and draw them sequentially:
std::vector<???> shapes;void DrawShapes(const std::vector<???>& shapes) { for(const auto& shape: shapes) { DrawSingleShape(shape); }}This example is far from practical; this is not polymorphism, but it can be seen as an example to understand the basic role of templates in type erasure. In the next section, we will introduce a practical implementation method for type erasure.2.2.2 Type Erasure ContainerClearly, we do not want a common base class, yet we want to achieve polymorphism, which requires something hardcore. A common approach is to design a container for concrete types that presents a unified type externally while expressing specific types internally. Klaus Iglberger provided such a solution in his CppCon 2022 talk, and we can use it to demonstrate the implementation idea of template-based external polymorphism.Assuming we design a container class for drawing elements called Shape, the template parameter for specific types cannot be designed as a parameter of Shape. If designed this way, we would get Shape<Circle> and Shape<Rectangle> as two completely different types, which is not conducive to the unified presentation of external types. A step back would be to design the constructor of Shape as a templated constructor to store specific types. There are various implementation ideas for encapsulating specific types internally; one can consider designing an abstract data type or using a union (which affects extensibility), or the simplest way is to use the PIMPL idiom. PIMPL is a typical dependency isolation measure and is also applicable to type erasure.This is the design of Shape given by Klaus Iglberger. Here, a small inheritance relationship is used; ShapeConcept is a constraint interface for specific behaviors supported by all Shapes, while also giving the m_pimpl pointer a unified type, thus isolating the dependency of the m_pimpl pointer from the specific type ShapeModel<ShapeT>. ShapeModel expresses the specific type of internal encapsulation, which saves the specific type of internal encapsulation through the template parameter ShapeT and is responsible for forwarding specific behavior requests from the interface to the underlying specific type.
class Shape {private: struct ShapeConcept { virtual ~ShapeConcept() = default; virtual void DoDraw(const Context& ctx) const = 0; };template<typename ShapeT> struct ShapeModel : public ShapeConcept { ShapeModel(ShapeT shape) : m_shape{ std::move(shape); } {} void DoDraw(const Context& ctx) const override { DrawShape(ctx, m_shape); } ShapeT m_shape; };std::unique_ptr<ShapeConcept> m_pimpl;public: template<typename ShapeT> Shape(ShapeT shape) : m_pimpl{std::make_unique<ShapeModel<ShapeT>>(std::move(shape))} {} void Draw(const Context& ctx) const { m_pimpl->DoDraw(ctx); }};The design of Shape should be based on value semantics, but given the existence of m_pimpl, it actually only supports moving by default. If we want to support copying, we need to consider copying m_pimpl, but this is not the focus of our example. What I want to say is that with the design of Shape, various shapes can play together without needing a traditional inheritance system:
void DrawShapes(const std::vector<Shape> & shapes) { Context ctx{ ... }; for(const auto& shape : shapes) { shape.Draw(ctx); }};int main() { std::vector<Shape> shapes; shapes.emplace_back(Circle{5.8}); shapes.emplace_back(Rectangle{15.0, 22.0}); shapes.emplace_back(Triangle{9.3, 3.6, 7.2}); DrawShapes(shapes);}Thus, the Triangle written by the neighbor can also be used; it only needs to adapt the provided drawing function on the Context to the DrawShape() style.This implementation method is also referred to as the “type erasure idiom” in some literature. Shape provides type erasure for the specific behavior of drawing shapes, and furthermore, it can easily extend support for other behaviors by simply adding behavior interface functions in ShapeConcept and calling the specific behavior implementation of the concrete class in ShapeModel. Compared to the “interface + implementation” method in section 2.1, this solution does not require a common base class for type erasure, and the type erasure is non-intrusive. For newly emerging types, support can also be easily provided, satisfying the OCP principle. Moreover, this solution does not have base classes and public interface inheritance, does not require manual dynamic memory allocation during use, does not directly use pointers, and does not require manual management of the lifecycle of objects, resulting in simple code with good performance.However, as you may have noticed, this solution mainly has two problems. The first problem is that the call to the DrawShape() function is hard-coded, which causes Shape to lose some flexibility. The second problem is the extension issue of ShapeConcept; if we want Shape to support more specific behaviors, we need to modify ShapeConcept, which violates the OCP principle. For the first problem, one can consider adding a std::function in ShapeConcept and extending the constructor to allow users to specify a callable object for specific actions when constructing Shape, thus solving the hard-coded issue of the drawing function based on Context. For the second problem, literature [6] also introduces a method to extend ShapeConcept without modifying it through multiple inheritance. Additionally, literature [5] introduces a design idea for a type erasure container based on virtual functions, which interested readers can research further.2.3 Other MethodsIf you do not want to make significant changes to create your own type erasure container or want to simplify the use of type erasure, you can consider using some type erasure containers provided by the standard library, such as std::function, which can express any type of callable object without needing to know the specific type of these callable objects (function pointers or lambdas) at the time of calling. std::any can encapsulate any type that supports copy construction (CopyConstructible), and combined with template techniques, it can also achieve type erasure. Moreover, Boost’s boost.typeerasure library is also a solution based on type erasure technology, which is currently one of the most robust and well-developed libraries, and can be used in many scenarios requiring type erasure technology when combined with boost.any.3 Topics Related to Type Erasure3.1 Object CopyingWhen an object is destroyed, it can be unaware of its specific type because the destructor can be virtual, but the constructor cannot be virtual. Therefore, when type erasure encounters the need to copy an object, it becomes troublesome. Using various casts to concretize the actual type and then using the actual type’s copy semantics to implement object copying is one approach, but it is clearly not the best choice. At this point, some patterns need to help, such as the Factory Method pattern, also known as “virtual constructors,” which is suitable for scenarios where the constructor type is not specific. However, I personally prefer using the Prototype pattern, where the object provides a Clone() method, which greatly reduces the design complexity of type erasure containers. For example, in the Shape example from section 2.2, we only need to add a Clone() interface method to ShapeModel to easily support the copy semantics of the Shape container:
class shape { struct ShapeConcept { ... virtual std::unique_ptr<ShapeConcept> Clone() const = 0; };template<typename ShapeT> struct ShapeModel : public ShapeConcept { ... std::unique_ptr<ShapeConcept> Clone() const override { return std::make_unique<ShapeModel>(*this); } };...// Copy constructor and copy assignment operator Shape(const Shape& other) : m_pimpl(other.m_pimpl->Clone()) {} Shape& operator=(const Shape& other) { Shape tmp(other); std::swap(m_pimpl, tmp.m_pimpl); return *this; }};3.2 Duck Typing
“If something looks like a duck, swims like a duck, and quacks like a duck, it might just be a duck”—this is the essence of duck typing. If two types do not share a common inheritance hierarchy but both provide the interfaces we expect and can work with the generic parts of the code, that is also a form of special polymorphism. Typically, duck typing is something that dynamic languages support, but with templates, strongly typed languages like C++ can also support duck typing without sacrificing type safety.
Duck typing usually works in conjunction with type erasure technology to implement the so-called template-based external polymorphism mechanism, as demonstrated in the example in section 2. Additionally, many traditional object-oriented design patterns, such as the observer pattern, also have template-based external polymorphism versions that do not require virtual functions and inheritance, and duck typing can work with them.
3.3 Optimization
Type erasure container classes typically adopt a value semantics design, so their copying, moving, and construction need to pay special attention to efficiency. Common optimization measures suitable for type erasure include Small Object Optimization (SOO), Copy-On-Write (COW), etc. The most common Small Object Optimization is the local buffer technique (or SBO), which you can see in various type erasure containers, such as std::function.
C++20 concepts can be used to constrain template parameters, preventing users from using meaningless types and enhancing type safety. For example, if we require duck types to have a member function named Draw(), we can write a concept and use this concept to constrain template parameters:
template<typename T>concept type_has_draw = requires(T t) { { t.Draw() };};template<type_has_draw ShapeT>struct ShapeModel : public ShapeConcept { ...};4 ConclusionThe difficult secret of software design is how to cope with change. One of the core points of identifying and managing change is to isolate dependencies at the appropriate level of abstraction to prevent the propagation of change. The type erasure idiom introduced in this article is a practical method to achieve dependency isolation by breaking the dependencies between types. Using an external polymorphism implementation scheme avoids cumbersome inheritance systems and facilitates working with new types that may emerge in the future (as long as the type is also a duck type conforming to specific behaviors), and it can also serve as a compile-time firewall (avoiding the need to recompile the entire library when adding new types).References
[1] C++ Type Erasure – Michael Hava
[2] C++ Type Erasure Demystified – Fedor G Pikus – C++Now 2024
[3] Klaus Iglberger, Breaking Dependencies – C++ Type Erasure – The Implementation Details, CppCon 2022
[4] Klaus Iglberger, Breaking Dependencies: Type Erasure – A Design Analysis, CppCon 2021
[5] Chris Cleeland, External Polymorphism An Object Structural Pattern for Transparently Extending C++ Concrete Data Types,
[6] Andreas Herrmann, Type Erasure with Merged Concepts, 2014
[7] Chris Wellons, Duck Typing vs. Type Erasure, 2014
[8] GOF, Design Patterns – Elements of Reusable Object-Oriented Software
[9] Dave Kilian, C++ ‘Type Erasure’ Explained, October 2014
[10] Zach Laine, Pragmatic Type Erasure: Solving OOP Problems with an Elegant Design Pattern, CppCon 2014
Information, Code, and Previous Articles
C++ common_reference
C++ override specifier
C++ std::common_type
C++ quoted manipulators
C++ std::addressof() function
C++ function family siblings
C++ std::function and its continuous evolution
Explanation of the article “C++ Small Objects by Value or by Reference”
C++ Small Objects by Value or by Reference
C++ CTAD and Deduction Guides
C++ all_of, any_of, and none_of
C++ 23 print and println
C++ format function supports custom types
C++ format and vformat functions (revised)
Content and Notification Summary