C++’s metaprogramming is always a peculiar beast. It seems like there is no real limitation to its power and the number of ways to misuse it.

In this case, while working on a library, I encountered an interesting problem for which finding a solution on Google wasn’t particularly productive – at least in the few minutes I spent trying to come up with a suitable query.

So here it is: I needed a map from types to values. The reason for this requirement remains somewhat obscure, but it was an intriguing exercise worth sharing.

The challenge with using types as keys is that maps rely on at least two key properties:

  • The ability to check for equality.
  • Either:
    • The ability to hash the key (producing a number that somehow represents the key).
    • The ability to order the key (determining if one key is “less than” another).

Types inherently possess the first property: std::is_same_v from the <type_traits> header readily provides this feature.

What about the other one? Well, there are actually several options available.

Obtaining a hash value that somehow represents the type, acknowledging that there may be collisions, is a tricky task. What are the properties of a type?

  • The name.
  • The members.
  • Its base classes.
  • Its size.

Now, if we exclude the use of typeid and macros1, and considering that C++23 didn’t introduce (once again) reflection, we are left only with size.

While this may seem challenging, it could actually work better than expected. However, implementing a compile-time hash map is a non-trivial task. I genuinely wanted something simple, just a few lines of code, to avoid creating the usual write-once-blame-forever templated abomination.

What about ordering? It turns out that std::type_info (returned by typeid) has a method called before specifically for the purpose of inserting items into a sorted container. However, I don’t want my code to depend on RTTI, and these methods are not constexpr, so I can’t use them at compile-time.

Nevertheless, there must be another, simpler way. Let’s explore further.

First of all, let’s define a type_map template, mainly characterized by its contained value type:

template <typename TValue>
struct type_map {
    // All definitions are here so that we can depend
    // on `TValue` without repeating it everywhere.
};

Each entry in a map needs to represent both the key and the value, which is seemingly straightforward:

    template <typename TKey>
    struct entry { TValue value; };

Now, how can we create a map with two entries for two different keys? The answer lies in inheritance!

You can easily define a map for keys like int, float, and std::string as follows:

    struct mymap: entry<int>, entry<float>, entry<std::string> {};

With this concept in mind, we can start writing a function to retrieve the value associated with a type.

The first decision to make is: What should we do if the map doesn’t contain the key? One option is to include a static_assert to halt compilation, or you can choose a more SFINAE-friendly approach. On the other hand, many maps allow you to specify a “fallback” value to return if the key is not present. This seems like a reasonable way to simplify our interface.

Regarding the function, it’s quite easy to come up with code using an if constexpr clause to select at compile-time the right behavior:

template <typename TKey, typename TMap>
constexpr static TValue get(const TMap& map, TValue fallback = {}) {
    if constexpr (std::is_base_of_v<entry<TKey>, TMap>) {
        const entry<TKey>& bucket = map; 
        return bucket.value;
    } else {
        return fallback;
    }
}

For the set function, we need to think once again about how this function will be used. It is clear that if we want things to be compile-time constant, we cannot mutate the state during the set phase. What we can do, instead, is return a new object with the new value.

The last question to solve is: how can we set a key that doesn’t have a bucket for yet? Luckily, we can return a different type, based on an if constexpr clause thanks to auto meta-type. Something like this is enough:

template <typename TKey, typename TMap>
constexpr static auto set(const TMap& map, TValue value) {
    if constexpr (std::is_base_of_v<entry<TKey>, TMap>) {
        auto newMap = map;
        entry<TKey>& bucket = newMap;
        bucket.value = value;
        return newMap;
    } else {
        struct composed : TMap, entry<TKey> {};

        return composed{ map, { value }};
    }
}

Now let’s have a look at the whole implementation:

template <typename TValue>
struct type_map {
    template <typename TKey>
    struct entry { TValue value; };

    template <typename TKey, typename TMap>
    constexpr static auto set(const TMap& map, TValue value) {
        if constexpr (std::is_base_of_v<entry<TKey>, TMap>) {
            auto newMap = map;
            entry<TKey>& bucket = newMap;
            bucket.value = value;
            return newMap;
        } else {
            struct composed : TMap, entry<TKey> {};

            return composed{ map, { value }};
        }
    }

    template <typename TKey, typename TMap>
    constexpr static TValue get(const TMap& map, TValue fallback = {}) {
        if constexpr (std::is_base_of_v<entry<TKey>, TMap>) {
            const entry<TKey>& bucket = map; 
            return bucket.value;
        } else {
            return fallback;
        }
    }
};

Less than 30 lines of code! Sweet.

Its usage is still a bit awkward though:

constexpr auto mymap = type_map<int>::set<type2>(
    type_map<int>::set<type1>(
        type_map<int>::set<type2>(type_map<int>{}, 10), 
        10
    ),
    20
);

constexpr auto type1value = type_map<int>::get<type1>(mymap); // = 10
constexpr auto type2value = type_map<int>::get<type2>(mymap); // = 20
constexpr auto notfound = type_map<int>::get<void>(mymap); // = 0

We can improve its usage by duplicating the get and set method and making it a template member function, instead of a free one. Unfortunately, we can’t define a template member in a class defined in a function. However, we can simply extract the composed concept:

template <typename TValue>
struct type_map {
    template <typename TKey>
    struct entry { TValue value; };

    template <typename TMap, typename TKey>
    struct composed : TMap, entry<TKey> {

        using self = composed<TMap, TKey>;

        template <typename T>
        constexpr auto set(TValue value) const {
            if constexpr (std::is_base_of_v<entry<T>, self>) {
                auto newMap = *this;
                entry<T>& bucket = newMap;
                bucket.value = value;
                return newMap;
            } else {
                return composed<self, T>{ *this, { value }};
            }
        }

        template <typename T>
        constexpr TValue get(TValue fallback = {}) const {
            if constexpr (std::is_base_of_v<entry<T>, self>) {
                const entry<T>& bucket = *this; 
                return bucket.value;
            } else {
                return fallback;
            }
        }
    };


    template <typename TKey>
    constexpr auto set(TValue value) {
        return composed<type_map<TValue>, TKey>{ {}, { value }};
    }

    template <typename TKey>
    constexpr TValue get(TValue fallback = {}) {
        return fallback;
    }
};

Which brings us to a much better interface:

constexpr auto mymap = type_map<int>{}
    .set<type2>(10)
    .set<type1>(10)
    .set<type2>(20);

constexpr auto type1value = mymap.get<type1>(); // = 10
constexpr auto type2value = mymap.get<type2>(); // = 20
constexpr auto notfound = mymap.get<void>(); // = 0

Much better!

  1. As everyone knows, macros are often discouraged, and one should exercise caution when using them, as the C++ community frowns upon their excessive use. :warning: BEWARE! ↩