Constraining Templates

A close friend of mine recently sat an interview for a junior c++ position. It was an initial interview just to see if she knew the language at all. In the age of AI passing an online assessment doesn't imply this. During the interview she was asked about templates and one of the questions related to constraining a templated function to only take Integral types. She was picking up the language for this interview and hadn't reviewed this syntax but the interviewer didn't seem to know the syntax either. As it turns out concepts were only introduced in c++20 and as such this syntax wasn't familiar to this engineering manager who likely hadn't written a line of code in the last decade.

Personally I don't envy either of them in this scenario. The antidote to this and topic of this article is to review concepts and compare them to the generics in my current "native language" Swift.

The primary idea of generics is to avoid code repitition. We can parameterize a piece of code over a type or value and then the same code can act differently depending on the type that is passed into it.

template <typename C, typename F>
auto map(const C& container, const F& function) {
    using Element = std::invoke_result_t<F, std::ranges::range_reference_t<C>>;
    std::vector<Element> newContainer{};
    for (const auto& item : container) {
        newContainer.push_back(function(item));
    }
    return newContainer;
}

One of my favourite examples is the above definition of the higher order function map. We define two generic parameters C and F. This syntax `template <typename C, typename F>` Bjarne Stroustrup claims this syntax should be thought of as "for all C and for all F" in math. Then we define the function as taking const references to these types. In the function we just use them as if we already know the type. Coming from other languages this is strange. In Swift, for instance, we would write this function as generic over the container and the output type of the function.

func newMap<C: Sequence, U>(C: container, function: (C.Element) -> U) -> [U]

You can see that, in order to iterate through the container, we need to tell the compiler that the container conforms to the sequence protocol. Moreover we need to specify the input and output types of the function so that the compiler knows that it is valid for us to call this function on the element of the container.

C++ has no such restrictions. This comes from a fact that is commonly touted by my Swift enthused colleagues. Swift has "real generics" where c++ just generates code. This claim comes from Swift using a witness table to have a single shared body of code accross different types. Although in practice this isn't always true in that Swift also often generates seperate code for performance reasons. In theory this is why c++ can so effectively duck type it's generics. The compiler looks at the places where this function is called and tries to generate code for each of these types. If this generated code compiles then the compiler is happy without thinking too much about what properties the types passed in share.

So with all this power why would a modern language like Swift not copy the c++ approach?

Well, it's kind of a mess. The compiler might not care what capabilities your types have but as a programmer, now that information is being stored in your head. The complexity hasn't gone away it's just you who needs to remember that C needs to be iterable and that F needs to be a callable that takes a unary argument of the type of the contents of C and returns the content type that matches the return type of the surrounding function. Moreover, programming is fundamentally a team sport and all of that information needs to be inferred by the next person who is unfortunate enough to stumble upon your code. And so C++ concepts appear.

template <
    std::ranges::range C,
    typename F
>

First, instead of writing our function to be completely generic "for all C and all F", we can constrain the types. "For all C and for all F where C is X and F is Y" The syntax for this is called a requires clause and the X and Y are called concepts

template <typename C, typename F>
requires std::ranges::range<C> 

The requires clause is used after a template to apply a boolean expression to list rules (called concepts). Now the concepts we are using here are provided by std but we can specify our own concepts.

// example of checking that C has pushback defined
// we won't actually use this for our map function
template <typename T>
concept PushBackConstructible = requires(C c, T v) {
    c.push_back(v);
};

When we are defining a concept the requires keyword is used again. This usage is called a requires expression. The code in the curly braces is checked for compilation in order to determine whether the concept is upheld. We can also use these expressions to define concepts inline. These are called ad-hoc constraints since we havent given them a name.

template <typename C, typename F>
requires requires(C c, T v) {
    c.push_back(v)
}
    && std::ranges::range<C>

That requires requires may look like a typo but it is correct syntax! But in my personal opinion it is a red flag and ad-hoc constraints like this should be avoided where possible.

With all we have learnt so far we have essentially added a single condition to our classic template function.

template <typename C, typename F>
requires std::ranges::range<C>
auto map(const C& container, const F& function) {
    using Element = std::invoke_result_t<F, std::ranges::range_reference_t<C>>;
    std::vector<Element> newContainer{};
    for (const auto& item : container) {
        newContainer.push_back(function(item));
    }
    return newContainer;
}

We can use it as follows

int main() {
    auto myValues = std::vector{1,2,3};
    auto intToInt = [](auto val) { return val + 2; };
    auto intToStr = [](auto val) { return std::to_string(val); };
    auto newInts = map(myValues, intToInt);
    auto newStrs = map(myValues, intToStr);
    for (auto i = 0; i < myValues.size(); ++i) {
          std::cout << "original " << myValues[i] << std::endl;
          std::cout << "intFunked " << newInts[i] << std::endl;
          std::cout << "strFunked " << newStrs[i] << std::endl;
    }
}

This works as expected

g++ --std=c++23 test.cpp && ./a.out
    original 1
    intFunked 3
    strFunked 1
    original 2
    intFunked 4
    strFunked 2
    original 3
    intFunked 5
    strFunked 3

But what happens when we make a mistake. Let's say we pass a function that takes the wrong parameter type.

int main() {
    auto myValues = std::vector{1,2,3};
    auto containerToVoid = [](std::vector<int> val) { val.push_back(1); };
    auto somethingStrange = map(myValues, containerToContainer);
}

This function gives us a difficult to parse wall of error text

  459 | using invoke_result_t = typename invoke_result<_Fn, _Args...>::type;
      | ^~~~~
./test.hpp:8:26: note: in instantiation of template type alias 'invoke_result_t' requested here
    8 |     using Element = std::invoke_result_t<F, std::ranges::range_reference_t<C>>;
      |                          ^

So let's try constraining this template parameter such that it can only take a function of the correct type. Now remember in Swift we defined the function as taking C.Element and returning element type of the container the map function returns. The important part of this is that we can't just pass anything into this parameter. It needs to be a closure and it needs to take an argument of the element type of our vector.

template <typename C, typename F>
requires std::ranges::range<C> &&
    std::invocable<F, std::ranges::range_reference_t<C>>

With this extra line we get a much clearer message.

test.cpp:8:29: error: no matching function for call to 'map'
    8 |     auto somethingStrange = map(myValues, containerToContainer);
      |                             ^~~
./test.hpp:9:6: note: candidate template ignored: constraints not satisfied [with C = std::vector<int>, F = (lambda at test.cpp:7:33)]
    9 | auto map(const C& container, const F& function) {
      |      ^
./test.hpp:8:5: note: because 'std::invocable<(lambda at test.cpp:7:33), std::ranges::range_reference_t<vector<int, allocator<int> > > >' evaluated to false
    8 |     std::invocable<F, std::ranges::range_reference_t<C>>
      |     ^

You might notice that the function we mistakenly passed not only didn't take the right input but also didn't return anything. We should constrain the output of our closure as well. We can make sure our output is non-void and that we can construct a vector out of it.

requires std::ranges::range<C> &&
    std::invocable<F, std::ranges::range_reference_t<C>> &&
    (!std::is_void_v<std::invoke_result_t<F, std::ranges::range_reference_t<C>>>) &&
requires {
    std::vector<std::invoke_result_t<F, std::ranges::range_reference_t<C>>>{};
}

And that's it. We have written a map function and then we improved our readability and the errors we will receive when we pass it mistaken input. Hopefully in future when we are asked to constrain a template to only take an integral type we will have some idea how to do it.

p.s the concept for that is std::integral