Efficient Way to Index Variadic Parameters

The introduction of variadic parameters (or template parameter packs) in C++11 made generic and meta-programming more powerful and approachable. A common need is to retrieve an element (a type or a value) from a pack via an index (aka indexing). This tutorial presents a user-friendly solution achieving this using modern C++ features.

But, is there a need?

To understand it, we first need to learn the problem statement.

Before C++11, there was no proper way to write a function with arbitrary arguments. There were multiple approaches, including using variadic functions, va_ family of macros, and ellipsis syntax. However, with time, it will become cumbersome to manage. One more problem with this approach is the type of unsafe issue that was very hard to get.

What is the solution?

Variadic templates. The templates allowed writing functions with arbitrary arguments. The approach is also type-safe as the arguments were handled at compile-time rather than run-time.

Compile-time handling opened up more possibilities as it gives the developer the power to tweak how they are handled.

In this tutorial, we will learn about a straightforward technique, where we will use a standard library template. It offers excellent performance and reliability.

What are Variadic templates

Before we get started with the code, we need to understand the concept of variadic templates. To do so, let’s check out a basic example below.

template<typename T>
T multi(T a){
    return a;
} 

template<typename , typename... Args>
T multi(T first_var, Args... args) {
    return first_var * multi(args...);
}

To call it, you can use any of the following ways.

long mul = multi(2,6,8,9);

This will multiply all the values and return the result in the mul variable.

Here, the multi function is designed to accept as many variables as possible. The function will work correctly in compile-time, where both checking and compilation is done at compile time.

All of these are possible with C++11, where the templating system now knows how to handle the inputs associated with a template function.

Another thing that you need to know is the “template parameter pack”. Here the parameter pack is typename… Args. The function parameter pack, on the other hand, is the Args…args.

With a clear understanding of Variadic templates, we are now ready to go through the main tutorial.

The basic idea

There are various techniques available that differ in compile-time performance. These multiple approaches aim to improve compile-time indexing performance. In his article, Louis Dionne, Efficient parameter pack indexing showed various library-based and compiler-tweak ways to improve performance.

One of the worse approaches was using recursion, which adversely affected the performance.

The most straightforward approach is to use the STL, which provides reliability and reasonable (as well as evolving) performance most of the time.

This is a common solution for type templates:

#include <tuple>

template <size_t N, typename... Ts> //this constraint will output a nicer more helpful error message in case of an out-of-bounds index //it also prevents usage with an empty pack, which would make no sense requires (N < sizeof...(Ts)) using nth_type = std::tuple_element_t<N, std::tuple<Ts...>>;

The type parameter pack is expanded into an std::tuple and the type retrieved at N-position via std::tuple_element_t.

static_assert( std::is_same_v< nth_type<1, int, unsigned, float>, unsigned > );

And for non-type (aka value) templates:

template <size_t N, auto... vals> requires (N < sizeof...(vals))
constexpr auto const nth_value = std::get<N>(std::tuple{vals...});

static_assert( nth_value<1, 10, 100ll> == 100ll );

A comprehensive solution

In this section, we will take a look at the comprehensive solution on how to manage the indexing of variadic parameters.

The goal is to handle both values and types without breaking the program or related performance.

Our end goal can be summarized as below.

It would be nice to have a unique simple to use solution handling both types and values, even wrapped as template parameters. Besides, in the case of an out-of-bounds index, the preferred behavior may not be a hard error but rather looping or returning void/zero.

Note: in order not to clutter up the text, keywords [[nodiscard]] and except have been omitted although they apply.

#include <tuple>
#include <limits>

//std::conditional-like branching used by a behavior implementation
template <bool>
struct ov_conditional { template <size_t, typename...> using type = void; };
template <>

struct ov_conditional<true> { template <size_t N, typename... Ts> using type = std::tuple_element_t<N, std::tuple<Ts...>>; };

template <size_t N>
struct nth
{

//this variable template returns the correct index if the last alias is used (see below)
template <typename... Ts>
static constexpr auto const index =
[] () constexpr {
if constexpr (N == std::numeric_limits<decltype(N)>::max())
return sizeof...(Ts) - 1; //returns last argument
else
return N;
}();

template <typename Derived>  //CRTP
struct behavior_base
{
//TYPES

//fetching the implementation in Derived
template <typename... Ts>
struct from_types_impl final { using type = typename Derived::template from_types_impl<Ts...>; };
 
template <template <typename...> typename Wrapper, typename... Ts>
struct from_types_impl<Wrapper<Ts...>> final { using type = typename from_types_impl<Ts...>::type; };

template <typename... Ts>
using from_types = typename from_types_impl<Ts...>::type;

//VALUES

//handling the case of values wrapped in a template
struct wrapped final
{
template <typename...>
struct from_values_impl;

//specializations to handle common cases

//notably handles std::integral_constant
template <template <typename T, T> typename... Wrappers, typename... Ts, Ts... vals>
struct from_values_impl<Wrappers<Ts, vals>...> final {
static constexpr auto const value = Derived::template from_values_impl(vals...);
};

//the equivalent for std::integer_sequence would the following, but gcc doesn’t like it
//template <template <typename T, T...> typename Wrapper, typename T, T... vals>
//struct from_values_impl<Wrapper<T, vals...>> final //internal compiler error

//thus falling back on a specialization handling std::integer_sequence exclusively
template <typename T, T... vals>
struct from_values_impl<std::integer_sequence<T, vals...>> final {

static constexpr auto const value = Derived::template from_values_impl(vals...);
};

template <typename... Wrappers>
static constexpr auto const from_values = from_values_impl<Wrappers...>::value;
};

template <auto... vals>
static constexpr auto const from_values = Derived::template from_values_impl(vals...);

//assignable version
template <auto&... vals>
static constexpr auto& from_refs = Derived::template from_values_impl(vals...);

template <typename... Ts>
static constexpr //also usable at compile-time
decltype(auto) //return type forwarding for lvalue reference assignment
from_args( Ts&&... prms ) {
return Derived::template from_values_impl( std::forward<Ts>(prms)... );;
}

//these overloads handle common cases like above for function parameters

template <template <typename T, T> typename... Wrappers, typename... Ts, Ts... vals>
static constexpr auto from_args( Wrappers<Ts, vals>&&... ) { return Derived::template from_values_impl(vals...); }

template <template <typename T, T...> typename Wrapper, typename T, T... vals>
static constexpr auto from_args( Wrapper<T, vals...>&& ) { return Derived::template from_values_impl(vals...); }
};

//implementation of behaviors

struct constrained final : behavior_base<constrained>
{
template <typename... Ts> requires (index<Ts...> < sizeof...(Ts))
using from_types_impl = std::tuple_element_t<index<Ts...>, std::tuple<Ts...>>;

template <typename... Ts> requires (index<Ts...> < sizeof...(Ts))
static constexpr decltype(auto) from_values_impl( Ts&&... prms ) {
return std::get<index<Ts...>>(std::forward_as_tuple(std::forward<Ts>(prms)...));
}
};

struct looping final : behavior_base<looping>
{
template <typename... Ts>
using from_types_impl = std::tuple_element_t<index<Ts...> % sizeof...(Ts), std::tuple<Ts...>>;

template <typename... Ts>
static constexpr decltype(auto) from_values_impl( Ts&&... prms ) {
return std::get<index<Ts...> % sizeof...(Ts)>(std::forward_as_tuple(std::forward<Ts>(prms)...));
}
};
struct or_void final : behavior_base<or_void>
{
template <typename... Ts>
using from_types_impl = typename ov_conditional< index<Ts...> < sizeof...(Ts) >::template type<N, Ts...>;

template <typename... Ts>
static constexpr decltype(auto) from_values_impl( Ts&&... prms )
{
if constexpr (constexpr auto const index_ts = index<Ts...>;
index_ts < sizeof...(Ts))
return std::get<index_ts>(std::forward_as_tuple(std::forward<Ts>(prms)...));
else
return 0;
}
};

using or_zero = or_void; //alias for values

using default_behavior = constrained;

//shortcuts

using wrapped = typename default_behavior::wrapped;

template <typename... Ts>
using from_types = typename default_behavior::template from_types<Ts...>;

template <auto... vals>
static constexpr auto const from_values = default_behavior::template from_values<vals...>;

template <typename... Ts>
static constexpr decltype(auto) from_args( Ts&&... prms ) {
return default_behavior::from_args( std::forward<Ts>(prms)... );
}
};

//convenience aliases

using first = nth<0>;
using single = first;
//particularly handy, leveraging numeric_limits (at this point the size of the pack is unknown)
using last = nth<std::numeric_limits<size_t>::max()>;

Testing

To make sure that our solution works as intended, we need to test our code. That’s why we will test each behavior including types and values.

Note: compiles on minimum gcc 8.1 with -c++17 and -fconcepts

At compile-time

To test the code at compile-time, we will be using the following code.

using std::is_same_v;

//TYPES

//testing each behavior
static_assert( is_same_v< nth<1>::constrained::from_types<int, unsigned>, unsigned > );
static_assert( is_same_v< nth<2>::looping::from_types<int, unsigned>, int > );
static_assert( is_same_v< nth<2>::or_void::from_types<int, unsigned>, void > );

//behavior can be omitted (default is constraint)
static_assert( is_same_v< nth<1>::from_types<int, unsigned>, unsigned > );

//transparent for wrapped types
static_assert( is_same_v< nth<1>::from_types< std::tuple<int, unsigned> >, unsigned > );

static_assert( is_same_v< first::from_types<int, unsigned>, int > );
static_assert( is_same_v< last::from_types<int, unsigned>, unsigned > );


//VALUES

static_assert( last::constrained::from_values<10, 20> == 20 );
static_assert( nth<2>::looping::from_values<10, 20> == 10 );
static_assert( nth<2>::or_zero::from_values<10, 20> == 0 );

//wrapped has to be specified for wrapped values
static_assert( first::wrapped::from_values<std::index_sequence<10, 20>> == 10 );
static_assert( last::wrapped::from_values< std::integral_constant<int, 10>, std::integral_constant<int, 20> > == 20 );

//----
auto const cvar = 20;
static_assert( last::constrained::from_args(10, cvar) == 20 );
static_assert( nth<2>::looping::from_args(10, cvar) == 10 );
static_assert( nth<2>::or_zero::from_args(10, cvar) == 0 );

//transparent for wrapped values as function parameters
static_assert( last::from_args( std::index_sequence<10, 20>{} ) == 20 );
static_assert( first::from_args( std::integral_constant<int, 10>{}, std::integral_constant<int, 20>{} ) == 10 );

At runtime
If you aim to test the behavior of the code, then you need to use the following code.

#include <cassert>

auto st_var = 0; //static linkage is needed

int main()
{    
    single::constrained::from_refs<st_var> = 5;
    assert(st_var == 5);

    auto var = 0;
    last::from_args(10, var) = 5;
    assert(var == 5);
}

Conclusion

This leads us to the end of our tutorial where we explore a unique way to solve the indexing of variadic parameters.

So, what do you think about the solution?