Type erased view types in C++

Type erasure is, in C++, 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 most famous classes 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

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:

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:

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.

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

This might work, but ct_map has the size as part of its type, similar 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 map_view would solve my issue.

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.

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

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

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.

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.

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 needs 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 separate files.

In practice, I believe it is better to make third-party classes conform to the std::map-API for making such classes work with map_view, instead of having many map_view subclasses with different implementations. If it is not possible to change the API of a custom map class, 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.