We previously looked into an interview question at Maven, demonstrating one solution using template metaprogramming to return the unique elements in a compile-time vector. This relied on moving control flow to compile-time by utilising recursive templates for looping and partial specialisation for selection. This reflects a form of template meta-programming usable in C++03. But with each version after C++11, the set of tools available for compile-time programming has increased.
To give an insight into how to apply a post-C++11 set of tools, we will revisit the same question using two different approaches of modern C++.
Given a vector:
template <int… I> struct Vector;
Assume the vector is sorted. Remove adjacent duplicates from the vector.
For example:
Given: Vector<1, 2, 2, 2, 3, 4, 4, 5>
Produce: Vector<1, 2, 3, 4, 5>
If the vector contains non-adjacent duplicates, it is expected that duplicates will remain
Given: Vector<1, 2, 2, 2, 3, 4, 4, 1, 5>
Produce: Vector<1, 2, 3, 4, 1, 5>
template <typename Vector>
struct uniq
{
using type = XXX;
};
It is invoked like so: uniq<Vector<1, 2>>::type. It can be verified with
static_assert(std::is_same_v<uniq<Vector<1, 2, 2, 2, 3, 4, 4, 5>>::type, Vector<1, 2, 3, 4, 5>>);
As always, our starting point should be a runtime version of the function so that we understand the control flow that must be converted to runtime:
auto uniq(std::vector<int> const& input)
{
std::vector<int> output;
if (!input.empty())
{
int previous = input.front();
output.push_back(previous);
for (int element : input)
{
if (element != previous)
{
output.push_back(element);
previous = element;
}
}
}
return output;
}
In brief, iterate through the values, and if they do not match the previous last element in the vector then add the new element, otherwise, drop it.
The fold expression approach
To begin we start with our definition of a compile-time vector of integers, and the primary template defining the declaration of our compile-time function.
template <int... I>
struct Vector {};
template <typename Vector>
struct unique; // Primary templateWe can use fold expressions introduced in C++17 to generate a compile-time loop, with the loop body provided in an overloaded binary operator. In this case, we use the plus operator, which has left to right precedence, but we could just as easily loop backwards by overloading a binary operator such as the equals operator that has a right to left precedence. The operator takes a vector of integers on the left-hand side and an integer, which must be passed as an integral constant to be used at compile-time due to the current lack of support for compile-time function parameters in C++. We provide an empty vector as the initial state for the fold, and at the end of the fold we get our result. As the result is the value returned by operator+ we use decltype to deduce the underlying type of the unique Vector and provide it in the type alias.
template <int... I>
struct unique<Vector<I...>>
{
using type = decltype((Vector<>{} + ... + std::integral_constant<int, I>{}));
};
template <int... I, int X>
constexpr auto operator+(Vector<I...> v, std::integral_constant<int, X> x);Now onto the loop body, which as mentioned is implemented by defining the plus operator. This is where we do the actual uniqueness computation. We must check if the integer parameter is equal to the last member of the vector, and if so, skip adding it to the vector, otherwise, it should append the integer to the vector.
Unfortunately, getting the last parameter of a parameter pack is not easy as non-trailing parameter packs cannot be deduced. So much so that a solution to this particular issue has been proposed for future revisions of the language. We could throw it into a tuple and just get the last element via the tuple’s functionality as follow:
template <int... I>
consteval auto last(Vector<I...>)
{
constexpr std::tuple t{I...};
constexpr auto N = std::tuple_size_v<decltype(t)>;
return std::get<N-1>(t);
}However, this relies on the machinery of std::tuple, which is not lightweight, in particular, many STL implementations use recursion to implement tuples to support compatibility with old versions of the language which incurs a compile-time performance cost. We can do better.
Using fold expressions we can fold on the comma operator to expand on the return statement. Return will ignore all but the last value, which is what we want. However, if we are compiling with full warnings the compiler will now raise a warning about unused values. To silence this warning we declare a lambda that performs an identity transformation and runs the values through this, which is enough to make the compiler happy.
constexpr auto last(auto... args)
{
constexpr auto identity = [](auto i) { return i; };
return (identity(args), ...);
}
Now all that remains is to select between the numerous conditions of the loop body. Selection in a constant context becomes much easier in the post C++17 world thanks to constexpr if, which allows different function implementations to coalesce in the same function body. Used in conjunction with auto return type deduction this allows the function body to return different types.
First, we can check if our last integer from our compile-time vector is the same. If so, we don’t want to add it to the vector, so we return the vector without the new value. Otherwise, we append it to the vector and return it. However, this will fail the first time the function is invoked with an empty vector, so we must add one more condition to check for a vector of zero elements, and in this case, we just append the new value to it.
template <int... I, int X>
constexpr auto operator+(Vector<I...> v, std::integral_constant<int, X> x)
{
if constexpr (sizeof...(I) == 0)
{
return Vector<X>{};
}
else if constexpr (last(I...) == x)
{
return v;
}
else
{
return Vector<I..., X>{};
}
}
All that remains is to put the pieces together, and we now have a meta-program for calculating the unique members of a compile-time vector that relies on techniques that are considerably more natural to the mental model required for runtime computations.
#include <type_traits>
#include <utility>
template <int... I>
struct Vector {};
template <typename Vector>
struct unique; // Primary template
template <int... I>
struct unique<Vector<I...>>
{
using type = decltype((Vector<>{} + ... + std::integral_constant<int, I>{}));
};
constexpr auto last(auto... args)
{
constexpr auto identity = [](auto i) { return i; };
return (identity(args), ...);
}
template <int... I, int X>
constexpr auto operator+(Vector<I...> v, std::integral_constant<int, X> x)
{
if constexpr (sizeof...(I) == 0)
{
return Vector<X>{};
}
else if constexpr (last(I...) == x)
{
return v;
}
else
{
return Vector<I..., X>{};
}
}
static_assert(std::is_same_v<unique<Vector<1, 2, 2, 2, 3, 4, 4, 5>>::type, Vector<1, 2, 3, 4, 5>>);
The constexpr calculation approach
However, that is only one approach to solving the problem. Another approach lies in using constexpr calculations and then transforming the value into type space. Let’s see how that would look; we start as before with our definition of a compile-time vector and our primary template for unique.
#include <algorithm>
#include <type_traits>
#include <utility>
template <int... I>
struct Vector {};
template <typename Vector>
struct unique; // Primary templateNow we specialise the unique type for use with compile-time vectors of a parameter pack of integers.
template<int... I> struct unique<Vector<I...>> {};Now, thanks to C++20 for making the std::unique algorithm constexpr, we can calculate the unique values for our compile-time vector by unpacking the values from type spaces directly into an array within the body of an immediately invoked constexpr lambda and storing them into a static constexpr data member.
template<int... I> struct unique<Vector<I...>>
{
static auto constexpr uniqueValues = []{
struct { int data[sizeof...(I)]; int size; } r{{I...}, sizeof...(I)};
r.size = std::unique(r.data, r.data + r.size) - r.data;
return r;
}();
};
Next, we define a helper lambda leveraging C++20’s template lambda syntax to convert from constexpr values back into type space. The lambda itself returns the result of an internally defined and immediately invoked lambda function.
The outer lambda uses std::make_index_sequence to generate a sequence of indices into our compile-time array. This sequence is passed to the inner lambda allowing it to unpack the array’s values from the outer lambda’s template type directly into the compile-time Vector’s template parameter list.
template<int... I> struct unique<Vector<I...>>
{
static auto constexpr uniqueValues = []{
struct { int data[sizeof...(I)]; int size; } r{{I...}, sizeof...(I)};
r.size = std::unique(r.data, r.data + r.size) - r.data;
return r;
}();
static auto constexpr toTypeSpace = []<auto p>(){
return []<std::size_t... J>(std::index_sequence<J...>) {
return Vector<p.data[J]...>();
}(std::make_index_sequence<p.size>());
};
};
Now to calculate the value of the unique compile-time vector we use decltype to query the return type of the toTypeSpace function, and we now have the type of our compile-time vector with unique elements only.
template<int... I> struct unique<Vector<I...>>
{
static auto constexpr uniqueValues = []{
struct { int data[sizeof...(I)]; int size; } r{{I...}, sizeof...(I)};
r.size = std::unique(r.data, r.data + r.size) - r.data;
return r;
}();
static auto constexpr toTypeSpace = []<auto p>(){
return []<std::size_t... J>(std::index_sequence<J...>) {
return Vector<p.data[J]...>();
}(std::make_index_sequence<p.size>());
};
using type = decltype(toTypeSpace.template operator()<uniqueValues>());
};
All that remains is to test and confirm that this works as expected. We can also clear up the use of the temporary uniqueValues and toTypeSpace values to provide us with our final, succinct solution. Using this technique we can solve not only unique but also any problem that can be solved using the constexpr STL algorithms of C++20.
#include <algorithm>
#include <type_traits>
#include <utility>
template <int... I>
struct Vector {};
template <typename Vector>
struct unique; // Primary template
template<int... I> struct unique<Vector<I...>> {
using type = decltype([]<auto p>(){
return []<std::size_t... J>(std::index_sequence<J...>) {
return Vector<p.data[J]...>();
}(std::make_index_sequence<p.size>());
}.template operator()<[]{
struct { int data[sizeof...(I)]; int size; } r{{I...}, sizeof...(I)};
r.size = std::unique(r.data, r.data + r.size) - r.data;
return r;
}()>());
};
static_assert(std::is_same_v<unique<Vector<1, 2, 2, 2, 3, 4, 4, 5>>::type, Vector<1, 2, 3, 4, 5>>);And that’s it! Two completely different approaches to solving the unique algorithm at compile-time, one leveraging fold expressions and the other constexpr functions. This example hopefully demystifies modern template meta-programming techniques by demonstrating a new set of tools for compile-time control flow in modern C++. Once these techniques are understood, solving compile time problems becomes a job of translating runtime algorithms to use a compile-time toolset.
