The C++ logo, by Jeremy Kratz, licensed under CC0 1.0 Universal

Type erased view types in C++


21 - 26 minutes to read, 5244 words
Categories: c c++
Keywords: c c++ constexpr constructor data structures immutable implementation detail inheritance inline iterator performance quick-bench std::span string_view type erasure

Type erasure

Type erasure, in C++, is type is a technique for representing a variety of concrete types through a single type.

In the C++ standard library, there are different examples of constructs that help to achieve type-erasure.

The first are std::string_view and std::span.

std::string_view provides a unified interface for std::string, literals, and const char*, while std::span does the same for containers holding continuous data in memory, like std::vector or arrays.

A typical example would be

size_t count_letter_A(const std::string& s) noexcept {
  return std::count(s.begin(), s.end(), 'A');
}

count_letter_A takes a const std::string& as a parameter, and is inefficient when the caller does not have a std::string because it needs to copy the content in it, and then discard it.

One could overload count_letter_A for const char* to support, \0-terminated strings, and add other overloads for other string types, like QString and MFC CString.

Another alternative would be to use a function template:

template <class S>
size_t count_letter_A(const S& s) noexcept {
  return std::count(s.begin(), s.end(), 'A');
}

but it does require some adjustments to work with const char* and other string types.

A better alternative, since C++17, is to use std::string_view, as it should be considered the fundamental non-owning string type to be used as a parameter:

size_t count_letter_A(std::string_view s) noexcept {
    return std::count(s.begin(), s.end(), 'A');
}

In this sense, std::string_view provides type-erasure, as count_letter_A can be used with std::string, \0-terminated strings, QString, CString from MFC, and a dozen of other string types, without any particular overhead (because all those classes use the same representation in memory, and std::string_view provides direct access to the data, without additional indirections.).

std::span works similarly for all containers that store the data in contiguous memory, like std::vector, arrays, or std::string.

Another example of type-erasure is given by std::any and std::function.

std::any can hold (as the name implies) any type of object, as long as it can be copied. std::function can hold everything that can be used as a function, like a structure with operator(), a function pointer, or a lambda.

Another example is provided by class hierarchies, like std::outstream.

The main difference between std::string_view and std::span, contrary to std::any and std::function, is that they do not own the data, and provide direct access to it. For those reasons, they are considered "lightweight" types, and you should pass them by copy to avoid further indirections. std::any and std::function do own the data, are considered "heavyweight" (like std::string), and add some overhead, as they generally need to allocate some memory and are opaque types. They are better passed as constant references to functions that do not need to make a copy or own the data.

A benefit of using type erasure is to minimize the amount of generated code. This makes it generally faster to compile.

When using templates, the compiler creates a different function for every type and is not always able to merge them back together, especially for bigger functions.

They also tend to be slower to compile, as everything needs to be in a header file, which can also have other drawbacks.

A type-erased map_view

The main reason I have explored this topic a little is that I wanted to have a type-erased view over maps.

The standard library provides std::map and std::unordered_map, but since I want to initialize constants at compile-time to avoid issues, so I have structures similar to ct_map that provides a std::map-like object that can be created at compile-time.

Those three map-like structures all have valid use cases, depending on the context.

This poses the question, what map should I use for functions that would take one by constant reference? Suppose I am taking const std::map<T, U>&, what do I do if my map has the "wrong" type?

The possible solutions are the same as those for the function count_letter_A.

Converting from one map to another is a possibly expensive operation, so it is a non-starter. Also duplicating every function is a non-starter.

A third possibility is to duplicate the function definition, and use internally a templated version; something like

// header file
void foo(const std::map<int,int>& m);
void foo(const std::unordered_map<int,int>& m);

// cpp file
namespace{
    template <class M>
    void foo_impl(const M& m){
        // implementation
    }
}
void foo(const std::map<int,int>& m){
    foo_impl(m);
}
void foo(const std::unordered_map<int,int>& m){
    foo_impl(m);
}

This might work, but ct_map has the size as part of its type, similarly to std::array, so this approach is not good enough, as I do not want to put the implementation of every function in header files.

A "lightweight" type-erased view_map would solve my issue.

Possible implementations

There are mainly two implementation techniques.

The first one is to use a class hierarchy. The parent class defines all supported operations, every subclass would wrap a map of a different type and act as a little facade.

The second one is to use void* (and reinterpret_cast).

Both approaches have advantages and disadvantages.

Class hierarchy

A possible implementation would look like

#include <utility>
#include <type_traits>
#include <functional>

#include <map>
#include <unordered_map>

template <class K, class V>
struct map_view {
  virtual const V& operator[](const K&) const = 0;
  virtual const std::size_t size() const noexcept = 0;
  virtual const std::pair<const K, V>* find(const K&) const = 0;
};

template <class K, class V>
struct std_map_view final : map_view<K, V> {
  const std::map<K,V>* pm;
  std_map_view(const std::map<K,V>& m) : pm(&m){}
  const V& operator[](const K& k) const override {
    return pm->at(k);
  }
  const std::size_t size() const noexcept override {
    return pm->size();
  }
  const std::pair<const K, V>* find(const K& k) const override {
    auto it = pm->find(k);
    return it == pm->end() ? nullptr : &(*it);
  }
};
template <class K, class V>
struct unordered_map_view final : map_view<K, V> {
  const std::unordered_map<K,V>* pm;
  unordered_map_view(const std::unordered_map<K,V>& m) : pm(&m){}
  const V& operator[](const K& k) const override {
    return pm->at(k);
  }
  const std::size_t size() const noexcept override {
    return pm->size();
  }
  const std::pair<const K, V>* find(const K& k) const override {
    auto it = pm->find(k);
    return it == pm->end() ? nullptr : &(*it);
  }
};

// subclasses for other types
// ...

Notice that std_unordered_map_view and std_map_view are identical, we can merge both implementation to only one, like

template <class M>
struct generic_map_view final : map_view<typename M::key_type, typename M::mapped_type> {
  const M* pm;
  generic_map_view(const M& m) : pm(&m){}
  const typename M::mapped_type& operator[](const typename M::key_type& k) const override {
    return pm->at(k);
  }
  const std::size_t size() const override {
    return pm->size();
  }
  const std::pair<const typename M::key_type, typename M::mapped_type>* find(const typename M::key_type& k) const override {
    auto it = pm->find(k);
    return it == pm->end() ? nullptr : &(*it);
  }
};

For simplicity, the next examples will use the two separate implementations, but the same point holds also for the unified implementation.

Also note that I’ve implemented operator[] in terms of at, as std::map::operator[] is not constant.

The class hierarchy approach has two big disadvantages.

The first is that you should not copy map_view. A copy would slice the class, as the copy-constructor of map_view has no idea of the member variables of its subclasses.

Also, its usage is not ideal, I would like to write

void foo(map_view<int, int> m);

std::map<int, int> m;
foo(m);
// or
foo(map_view(m));

But it will not compile, as map_view only has a default constructor.

On needs to write

void foo(const map_view<int, int>& m);

std::map<int, int> m;
foo(std_map_view<int, int>(m));

which is far less than ideal, as one needs to know which subclass to instantiate.

This can be mitigated by introducing factory functions:

template <class K, class V>
std_unordered_map_view<K,V> make_view(const std::unordered_map<K,V>& M){
  return std_unordered_map_view<K,V>(m);
}
template <class K, class V>
std_map_view<K,V> make_view(const std::map<K,V>& M){
  return std_map_view<K,V>(m);
}

at least the end-user does not need to spell the exact type out.

void foo(const map_view<int, int>& m);

std::map<int, int> m;
// or
foo(make_view<int, int>(m));

Also note that foo does not take map_view by value, which for a non-owning type feels strange, as it adds an unnecessary indirection.

Another note is that the destructor is not virtual. You might want to make it if you are going to store a std_map_view* int a map_view*. For the use-cases I’m designing map_view, to be used as a replacement for function parameters like const std::map<K, V>&, const std::unordered_map<K, V>& and similar, this is not striclty necessary.

void* and reinterpret_cast

The main idea is to save the information of what class we are going to type-erase during construction, and reinterpret_cast the void* back to its original type at every operation.

A naive approach

Let’s begin with type-erasing std::map:

template <typename K, typename V>
class map_view {
 const void* ptr;
 public:
 map_view( const std::map<K,V>& m) noexcept
    : ptr{ std::addressof( m ) }
     {}

 auto operator[](const K& k) const { return reinterpret_cast<const std::map<K,V>*>(m)->at(k); }
 const std::pair<const K, V>* find(const K& k) const {
   const auto& m = *reinterpret_cast<const std::map<K,V>*>( ptr );
   auto it = m.find(k);
   return it == m.end() ? nullptr : &(*it);
 }

 std::size_t size() const noexcept { return reinterpret_cast<const std::map<K,V>*>(m)->size(ptr); }
};

So far, so good.

Now we want to add support for std::unordered_map

template <typename K, typename V>
class map_view {
 const void* ptr;
 int type;
 public:
 map_view( const std::map<K,V>& m) noexcept
    : ptr{ std::addressof( m ) }, type(1)
     {}
 map_view( const std::unordered_map<K,V>& m) noexcept
    : ptr{ std::addressof( m ) }, type(2)
     {}

 auto operator[](const K& k) const {
   switch(type){
     case 1: return reinterpret_cast<const std::map<K,V>*>(m)->at(k);
     case 2: return reinterpret_cast<const std::unordered_map<K,V>*>(m)->at(k);
   }
 }

 const std::pair<const K, V>* find(const K& k) const {
   switch(type){
     case 1: {
       const auto& m = *reinterpret_cast<const std::map<K,V>*>( m );
       auto it = m.find(k);
       return it == m.end() ? nullptr : &(*it);
     }
     case 2: {
       const auto& m = *reinterpret_cast<const std::unordered_map<K,V>*>( m );
       auto it = m.find(k);
       return it == m.end() ? nullptr : &(*it);
     }
   }
 }

 std::size_t size() const noexcept {
   switch(type){
     case 1: return reinterpret_cast<const std::map<K,V>*>(m)->size();
     case 2: return reinterpret_cast<const std::unordered_map<K,V>*>(m)->size();
   }
 }
};

Adding support for std::unordered_map shows the main drawback of this approach; we need to know all types we do support, and "register" it to a member variable for doing the correct cast. We also need to implement a switch in every function, and nearly copy-paste the implementation in every case.

A possible alternative would be to store function pointers. A similar approach would be using member functions

int& at_fun_map( const void* ptr, const int& k ) -> const V& {return reinterpret_cast<const std::map<int, int>*>( ptr )->at(k);}
int& at_fun_unordered_map( const void* ptr, const int& k ) -> const V& {return reinterpret_cast<const std::unordered_map<int, int>*>( ptr )->at(k);}
// other free functions

template <typename K, typename V>
class map_view {
  using at_fun_t = const V&(const void*, const K&);
  using find_fun_t = const std::pair<const K, V>*(const void*, const K&);
  using size_fun_t = std::size_t(const void*);

  const void* ptr;
  at_fun_t* at_fun;
  find_fun_t* find_fun;
  size_fun_t* size_fun;

  public:

 map_view( const std::map<K,V>& m) noexcept
    : ptr{ std::addressof( m ) },
      at_fun(&at_fun_map)
      // assign other functions
     {}
 map_view( const std::unordered_map<K,V>& m) noexcept
    : ptr{ std::addressof( m )},
      at_fun(&at_fun_unordered_map)
     {}

     auto operator[](const K& k) const { return at_fun(ptr, k); }
     const std::pair<const K, V>* find(const K& k) const { return find_fun(ptr, k); }
     std::size_t size() const noexcept{ return size_fun(ptr); }
 };

This approach removes the need for the switch statement but has the drawback that we need to write all overloads for different std::map and std::unordered_map types.

A more robust implementation

Why register types by hand, if we can tell the compiler to do the work for us? After all, in the case of the class hierarchy, I’ve used templated subclasses instead of writing a subclass for every specific map type.

All functions have exactly the same implementation; it’s just the type we are casting to, and thus the function we are calling internally, that is different.

Thanks to lambdas, it is easy to remove all free functions and create only one templated constructor for every map-like structure.

template <typename K, typename V>
class map_view {
 using at_fun_t = const V&(const void*, const K&);
 using find_fun_t = const std::pair<const K, V>*(const void*, const K&);
 using size_fun_t = std::size_t(const void*);

 const void* ptr;
 at_fun_t* at_fun;
 find_fun_t* find_fun;
 size_fun_t* size_fun;

 public:
  template <class T>
  map_view( const T& m) noexcept
     : ptr{ std::addressof( m )  },
       at_fun{+[]( const void* ptr, const K& k ) -> const V& {return reinterpret_cast<const T*>( ptr )->at(k);}},
       find_fun{+[]( const void* ptr, const K& k ) -> const std::pair<const K, V>* {
            const auto& m = *reinterpret_cast<const T*>( ptr );
            auto it = m.find(k);
            return it == m.end() ? nullptr : &(*it);
       }},
       size_fun{+[]( const void* ptr) -> std::size_t {return reinterpret_cast<const T*>( ptr )->size();}}
      {}

      auto operator[](const K& k) const { return at_fun(ptr, k); }
      const std::pair<const K, V>* find(const K& k) const { return find_fun(ptr, k); }
      std::size_t size() const noexcept{ return size_fun(ptr); }
  };

Some observations.

The lambdas created in the constructor of map_view are stateless, as the state is passed as an additional parameter. Because of this, they can be converted to normal function pointers and stored inside map_view.

As lambdas all have unique types (the lambda [](){} does not have the same type of [](){}), it would not be possible to store them directly in map_view and accomplish type-erasure at the same time.

The function pointers of different map types T all have the same type; the type does not depend on T, even if this is used internally.

Using function pointers provides two advantages to the class hierarchy.

First, map_view can be copied. There is no slicing, and copying is cheap. Also a map_view initialized with a std::map can be reassigned to a map_view initialized with a std::unordered_map. This is the behavior one would expect after working with types such as std::string_view and std::span, or generally with value semantic.

Second, but not less important, is the fact that it can be used as expected when used as a function parameter, without spelling map_view out (if the constructor is implicit):

void foo(map_view<int, int> m);

std::map<int, int> m;
foo(m);

This is exactly the behavior that makes it simple to upgrade existing functions signature, without rewriting all the code using foo, unless foo is stored somewhere as a function pointer.

If for some reason the constructor should not be implicit, it is still better than using the class hierarchy, as one can write

void foo(map_view<int, int> m);

std::map<int, int> m;
foo(map_view<int, int>(m));

Still, there is one disadvantage.

When using void* and function pointers, sizeof(map_view) increases when we add new functionalities. The given implementation has the size of void* and the size of three function pointers (plus padding, if any).

As the main reason for having a type-erased view type is to be used as a function parameter, it is probably not an issue.

But it still bugged me, especially because the approach with virtual inheritance has a fixed size (on GCC, Clang, and MSVC), it does not matter how many virtual member functions there are.

Handwritten outline virtual tables

I’ve already written something down about handwritten virtual tables, and for those use-cases, I did not think at all about the size of the structures, as storing them in containers was not really an expected operation.

But for map_view it might make sense, and it occurred to me that in fact map_view is a class with a handwritten virtual table.

Contrary to my virtual table, the compiler (at least GCC, Clang, and MSVC) normally stores that somewhere else, and saves in the structure a pointer to it.

This explains why with one approach the size is constant and with the other not.

For the sake of completeness, (and because I was curious) I decided that I wanted to compare a version with an "outline" (and not "inline") handwritten virtual table:

template <typename K, typename V>
struct map_functions{
  using getkey_fun_t = const V&(const void*, const K&);
  using find_fun_t = const std::pair<const K, V>*(const void*, const K&);
  using size_fun_t = std::size_t(const void*);

  size_fun_t* size_fun;
  getkey_fun_t* op_square;
  find_fun_t* find_fun;
};

template <typename K, typename V>
struct map_view {
  const void* ptr;
  const map_functions<K,V>* f;

  template <class T>
  map_view( const T& m) noexcept
   : ptr{ std::addressof( m ) },
     f{
         [](){
               static constexpr map_functions<K, V> f_{
                 +[]( const void* ptr) -> std::size_t { return reinterpret_cast<const T*>( ptr )->size();},
                 +[]( const void* ptr, const K& k ) -> const V& {return reinterpret_cast<const T*>( ptr )->at(k);},
                 +[]( const void* ptr, const K& k ) -> const std::pair<const K, V>* {
                          auto& m = *reinterpret_cast<const T*>( ptr );
                          auto it = m.find(k);
                          return it == m.end() ? nullptr : &(*it);},
               };
               return &f_;
         }()
     }
    {}
    std::size_t size() const noexcept{
      return f->size_fun(ptr);
    }
    auto operator[](const K& k) const {
      return f->op_square(ptr, k);
    }
    const std::pair<const K, V>* find(const K& k) const {
      return f->find_fun(ptr, k);
    }
};

The implementation is similar to the "inline" approach, but we need to store the data in a separate (global) structure and create a reference to it.

Similar to what compilers do for virtual functions, we have traded some space in exchange for an additional indirection.

Which approach is the most efficient?

No notes about C++ comparing different techniques should not write something about performance.

So I’ve run some tests on quick-bench…​

The first test result was a little bit schocking.

Even if virtual functions are considered slow, function pointers are more or less the same thing. Thus a 120 times slower implementation does not make sense, but the result is reproducible.

By replacing for(int i = 0; i != 100; i) j+=m.find(-1)->second;` with `for(int i = 0; i != 100; i) j+=m.find(i)→second;, the result is more like something I would have expected, as all approaches behave similarly.

By giving a closer look, in the case of no indirection and function pointers, the compiler sees that the same function is called with the same parameter all the time, and avoids repeating the calls. Apparently, Clang is not able to do so with the virtual function.

Thus from a performance point of view, with Clang virtual functions are less optimized, but this alone should not be an argument for writing a virtual table by hand.

Code bloat

Another metric is how much code bloat is generated. Just like benchmarks, this also depends on the used compiler and compiler settings:

the difference does not seem to be significant.

But without optimization:

the class hierarchy is the clear winner, as there are fewer wrapper functions that are easy to inline with optimizations enabled.

The difference in code bloat (when using optimizations) can probably be more appreciated when one considers not only the function where the map_view is used but also the place where it is constructed.

In this example, the difference is more significant. For a bigger project, it depends on how many times such types are erased before the difference should not be ignored.

Build times

Build times of handwritten virtual tables are significantly slower, but I suspect that the test-case is not significant, as everything is on one file.

By not using std::addressof, and thus removing #include <memory>, the build times are mcu more similar. I am not sure how the handwritten virtual table can compile faster than no indirections at all.

A benchmark comparing bigger functions and templates over different files might be more significant, but I do not think that doing something like that on build-bench is possible.

Open issues

Those who paid attention will have noticed I cheated when implementing the member function find. Both std::map and std::unordered_map return an iterator, while map_view returns a pointer to a std::pair<K,V> or nullptr.

The issue is that different maps use different types of iterators, and somehow it is necessary to type-erase them too. In the case of find returning a pointer might be sufficient. It is definitively not sufficient for begin and end, as with the pointer it is not possible to iterate over the map.

One can consider different approaches, even if I’ve not written all details down.

The first thing to do is to acknowledge that just like we wrote a view for a map, we need to type-erase the iterator too.

But what data should the iterator return when dereferenced? std::map and std::unordered_map use std::pair<const K, V>&, but I want to use map-view with std::span too, as a std::span<V> is a map from integers to V!

Creating a std::pair<const K, V>& is not as simple, as an array does not store it, it stores only V.

The first idea one might have is to return a copy: std::pair<K, V>. Unfortunately, this might be expensive, and even if, it is generally not always possible.

Another approach would be to destructure the pair, and return std::pair<const K&, const V&>. This is not expensive, and permits to use map_view on maps that do not use std::pair internally.

It also seems to work for an array, as in the case of std::span, the iterator can hold a temporary index and create a reference out of it.

Unfortunately, this would break code like

auto it = m.begin();
const auto& kv = *it;
// changes the key in kv, but not the value,
// there is not only an unexpected mutation, but it also creates an inconsistent state
++it;

Another attempt would be to special case map_view<int-like, T> to return the value to K instead of a reference.

In other words, return std::pair<K, const V&> when K is int-like, and return std::pair<const K&, V&> for all other cases.

I’m not sure how good or bad this approach is, as it feels a lot like vector<bool>.

It also does not solve the general issue when a map-like class does not store the key anywhere (just like std::span).

For example, one could use a type-safe index like struct index{int value;}; instead of an int as a key; the underlying implementation would just extract value from index and use it as an index on an array. One could make more complex rules, like return by value if the key is cheap to copy, but such rules are difficult to express clearly, and this type of complexity is normally undesired.

A simpler approach is to drop the idea to provide iterators, and instead create a traverse function, that takes a callback. The callback would take the key and value by const-reference.

This solves all the issues, except that it is a very different API. This is problematic as it makes it hard to change an existing function taking a map by constant reference by another taking a map_view. It also makes it hard to reuse the algorithms of the standard library or other libraries.

Thus, as long the map stores both the key and the value, writing an iterator that returns a std::pair<const K&, const V&> seems the best solution. It works well because I am interested in a view as in string_view, I only want to provide non-mutable access to the data.

I would like to support maps that do not store the key directly, like an array, but there seems to be no good iterator definition. And without iterators, map_view loses a lot of functionalities.

Differences to other type-erased objects

map_view tries to be as lightweight as std::string_view or std::span, but has one difference. It adds at least one indirection and does not provide direct access to the data.

The benchmark is promising and shows that in general, the overhead is not that big, especially with GCC, but you are at the mercy of the compiler and other properties of the environment.

This makes it a viable alternative to templating functions that should work with different map types. map_view is more lightweight than std::any or std::function, as it does not own the data, thus it is ideal to be used as a parameter.

Conclusion

technique unified constructor sizeof fixed casts double indirections value semantic class hierarchy no yes*

no

yes*

no

manual inline vtable

yes

no

yes

no

yes

Values marked with "*" are to denote that it depends on the compiler, but GCC, Clang, and MSVC agree with what is reported in the table.

"unified constructor" means that there is one "entry point" for creating a map_view, ie the user just need to call map_view( /* params */). This also implies that there is one implementation on one file, unlike in the case of a class hierarchy where new classes can be added on other files.

In practice I believe it is better to make you class conform to the std::map-API for making you class work with map_view, instead of having many map_view sublcasses with different implementations. IF you cannot change the API of your map, it is always possible to write a thin non-owning wrapper convertible to map_view. It also has the advantage that this wrapper can be used in templated code that already works with std::map.

To sum it up:

A class hierarchy is the easiest and less error-prone to implement (no casts and less code to write) a type-erased view. On the other hand, it provides the worst interface. The type-erased view cannot be copied and cannot be constructed implicitly.

For an internal, localized API, this might be good enough.

For a public API or an internal API with a broader scope, I think the effort of using reinterpret_cast is well spent for providing an easier-to-use (and slightly more efficient) map_view type. In this case, the type-erased view is even trivially copyable and can be made implicitly constructible.

There is another difference not mentioned until this point: a class hierarchy can be used at compile time since C++20 (in a constexpr function). As reinterpret_cast can only be used at runtime, in general, the functions of a type-erased view with a handwritten virtual table can only be used at runtime. The view itself can be constructed at compile-time too (since C++20, as std::addressof has been marked as constexpr).

Considering the use-case I had, this is not extremely relevant, except for the construction part, if a type-erased type is used as constant. If the function is constexpr, then the whole implementation needs to be public/in a header file, and thus inline. In that case, using a templated function does not have that many disadvantages over a normal function.


Do you want to share your opinion? Or is there an error, some parts that are not clear enough?

You can contact me here.