C++20: SFINAE vs. Concepts

2024-06-30

Introduction

I recently wanted to port some python code to c++ (latency reasons) and I quickly realised it was not going to be a trivial port.

It required some template metaprogramming trickery and in the process I found myself writing my first c++ concept 1.

It’s fair to say that the original python code wasn’t the best, as I’ll explain in a moment, so it ended up being better, in practise, to not use this code…But it was fun and interesting to write so why not write about it here.

Caveat: I am not a template metaprogramming expert so it’s possible there are better ways to do this than those presented here!

The python code

The task is quite simple, several functions in the python module needed to take nested dictionary and return the values of the deepest level of nesting. In some instances there were three levels of nesting, i.e.

Dict[X, Dict[Y, Dict[Z, W]]] -> List[W]

for hashable types X, Y, Z and any type W, and some types have no nesting at all (i.e. just regular key value map where the values were non-dictionary types). Fortunately, in this application the level of nesting was fixed for all keys.

A simplied version of the python code would read something like this

def extract_values_helper(map_type):
    for value in map_type.values():
        if isinstance(value, dict):
            yield from extract_values_helper(value)
        else:
            yield value

def extract_values(map_type):
    return list(extract_values_helper(map_type))

This isn’t great code to begin with because a nested dictionary is completely un-typed, each time we want to access some data we have to remember what the keys at each level of nesting correspond to…and if we screw up and confuse the meaning of the keys then we’re met only with an unhelpful KeyError exception.

Nevertheless, let’s try and port this to c++

c++: The return type

The first question is what the return type of our function should be. In python we don’t have to offer a type, or we can specify List[W] as above. In either case the python interpreter won’t use the type information but in c++ it’s more interesting.

We could require that the caller of extract_values gave, as a template parameter, the type of the values at the end of the nested map, but it’ll be easier for a user if we infer it ourselves and makes the task more interesting anyway!

So, to find the type we want we first need to write something which can differentiate between map-like types and other types, then we need to iterate through the nested type until we find a non-map type.

The first part of this is quite straightforward, we’ll use the presence of T::key_type and T::mapped_type on map types in c++ (STL types like std::map and std::unordered_map 2 3, but also some nice alternatives such as absl::flat_hash_map 4):

template <typename, typename = void>
struct is_map_like : std::false_type
{
};

template <typename T>
struct is_map_like<T, std::void_t<typename T::key_type, typename T::mapped_type>> : std::true_type
{
};

Here, we define a class template which takes two template parameters and has two specialisations.

The first specialisation is a default case, it doesn’t utilise the second template type and derives from std::false_type. The second specialisation uses the second template argument to check that T has a key_type and a mapped_type, if it does then std::void_t will pass void-type as the second argument, and if not SFINAE (‘Subsitution Faliure Is Not An Error’, the worst acronym in all of c++) will kick in and the specialisation will be deleted.

With this in hand we can focus on recursively iterating through the map type until we reach not is_map_like.

That looks like this:

template <typename T, typename = void>
struct nested_value_type {
    using type = T;
};

template <typename T>
struct nested_value_type<T, std::enable_if_t<is_map_like<T>::value>>
{
    using type = typename nested_value_type<typename T::mapped_type>::type;
};

This is similar to is_map_like in that we are using the second template parameter to conditionally disable a class template. In the first specialisation we simply take a type T as a type alias named type, this is the default case. The second specialisation is enabled only if T is is_map_like, and if that is the case then we define type by recursion; we say that it is defined as the type of nested_value_type invoked with the mapped_type of T (which we know exists since the std::enable_if_t check has cleared it).

After all of that we can start to write the signature of our function!

auto extract_keys(const M& map_type) ->
    std::vector<nested_value_type<M>::type>;

c++: A SFINAE implementation

Now we can solve the full problem

template <typename M, typename S>
std::enable_if_t<not is_map_like<M>::value, void>
extract_values_helper(const M& v, S& values) {
    values.push_back(v);
}

template <typename M, typename S>
std::enable_if_t<is_map_like<M>::value, void>
extract_values_helper(const M& map_type, S& values) {
    for (const auto& [k, v] : map_type) {
        extract_values_helper(v, values);
    }
}

By now this should all look pretty reasonable: The is_map_like == true version iterates over the mapped values in the map and recursively calls extract_values_helper, the is_map_like == false version simply adds a value to the vector to be returned.

The only twist here is that the SFINAE is snuck in with the return type - if the first boolean template parameter is true, the second template type is returned (giving us a null return type), if it fails the template specialisation is rejected. We could put it in the template parameter pack, but it’s more complicated since std::enable_if_t isn’t a standard type so it gets a bit messy.

And lastly some code to call these helper methods:

template<
    typename M,
    typename I = nested_value_type<M>::type,
    typename V = std::vector<I>
>
auto extract_keys(const M& map_type) -> V
{
    V values;
    extract_values_helper(map_type, values);
    return values;
}

c++: Concepts

That works well enough but c++ std20 introduced concepts 1 so we should use them. We can use them re-define is_map_like as follows

template <typename M>
concept is_map_like = requires(M m) {
    typename M::key_type;
    typename M::mapped_type;
};

This checks the same conditions as our SFINAE, though we can also use concepts to assert that template types satisfy more general constraints e.g. that they have member functions with certain signatures, that they are default constructible etc.

With this, we can start to simplify the rest of our code:

template <typename T, typename = void>
struct nested_value_type {
    using type = T;
};

template <is_map_like T>
struct nested_value_type<T> {
    using type = typename nested_value_type<typename T::mapped_type>::type;
};

where we can avoid the previous std::enable_if_t business by specifying with the concise is_map_like T in our template parameter pack. We can even get away with a single helper function:

template <typename M, typename S>
void extract_values_helper(const M& map_type, S& values) {
    if constexpr (is_map_like<M>) {
        for (const auto& [key, vals] : map_type) {
            extract_values_helper(vals, values);
        }
    } else {
        values.push_back(map_type);
    }
}

which reads almost the same as our python isinstance code, pretty neat!

Conclusion

A simple port of a snippet of python code turned into a bit of an adventure into template metaprogramming in c++!

It is worth noting that neither of these c++ implementations have a property which the python version has - the python extract_values_helper is a generator i.e. it contains the yield keyword. This means that we could choose to iterate over the values of our nested map using O(1) additional memory if we didn’t actually want them all returned as list. This might not seem like a big deal but if the ’leaf’ values of our nested map had a big memory footprint and we had millions of them then our c++ code would most likely run into some difficulties.

Two ways around this spring to mind:

  • We could write a version which returned a container of std::reference_wrapper<T> 5
  • We could try c++’s newly added coroutines (which I believe are a bit like python generators) 6

Here are godbolt links for the SFINAE version 7 and the concepts version 8 if you want to see the code in action.

References

  1. C++ Constraints and Concepts ↩︎

  2. std::map ↩︎

  3. std::unordered_map ↩︎

  4. Abseil maps ↩︎

  5. std::reference_wrapper ↩︎

  6. C++ coroutines ↩︎

  7. godbolt: SFINAE ↩︎

  8. godbolt: Concepts ↩︎

Jack Medley
Jack Medley
Head of Research, Gambit Research

Interested in programming, data analysis, optimisation and Bayesian statistics