This article is not a good explainer of type erasure because it uses inheritance to do it.

I’m waiting for the day that someone figures out and does a blog post showing that every std data structure can be rewritten with type erasure.

Here’s how it works:

Let’s use vector because it’s simple. This vector impl works with just plain void* memory with no type information.

The vector type wrapper (matching std::vector) is a template but instead of recreating the entire data structure with a different type, it will instead create the void* implementing vector in a unique_ptr and pass boiler plate functions so that the vector know how to: 1. the size of T 2. in place constructor of T at the void* 3. in place destructor of T at the void* 4. A copy constructor of T at void* src, dst.

The wrapper vector<T> that owns the vector impl then does the necessary casts back to T. For example vector::at could be implemented as such:

  <template typename T>
  class vector { // type wrapper.
    T& at(size_t i) {
      void* p = vector_impl_->get(i);
      T* t = static_cast<T*>(p);
      return *t;
    }
  ...
  }

In this example, vector<T> wrapper would still be inlined everywhere, however VectorImpl could be defined exactly once in a cpp file. The template bloat problem is reduced from the entire data structure to just the wrapper casting back and forth from void* <—> T&.

This can be extrapolated to complex algorithms like std::map. And as a bonus the polymorphic wrapper can do all the boiler plate generation so that the interface could be made to match the std::map.

Testing the bloat size reduction could be performed on a code base with significant usage of std map across multiple types, and see if the optimizing compiler will reduce the final binary size with the type erased map swapped in.