Building, say, indices<6,4,2,0,-2,-4>

Published: by Creative Commons Licence

A simple indexing class of variadic std::size_t template parameters is often used to provide a structured method to select multiple elements from a C++11 tuple. In this post I present an alternative to this interface, commonly used when building an object of this type, wherein a finite series of indices is now generated according to a numeric range and signed stride; akin to Fortran array section syntax. Let's look at the common solution first.

A tuple may be created either using the std::tuple constructor, or std::make_tuple function template. Both expect the same variadic series of arguments. In addition, the constructor requires the type of each argument explicitly. Hence, the more concise std::make_tuple, is used throughout the examples. In the example below, the last element of t1 will be an int.

auto t1 = std::make_tuple('z',false,42,"cat",7);
auto t2 = std::tuple<char,bool,int,const char *,long>('z',false,42,"ktn",7);

Selection of a single tuple element is achieved using the standard tuple function template: std::get. The sole template parameter of std::get, a std::size_t, represents an index; and must be a constant expression. Using the t1 tuple from the code above, std::get<4>(t1) evaluates to an int; with a value of 7.

As a variadic function template, std::make_tuple can of course be used to create a new tuple from the elements of another. In the code below, t3, having type tuple<char,int,int>, is formed from copies of the 1st, 3rd, and 5th elements from the earlier tuple, t1.

auto t3 = std::make_tuple(std::get<0>(t1),std::get<2>(t1),std::get<4>(t1));

In the code above, we hard coded the selection using three index values: 0, 2, and 4. How could we instead write a function template, select, that accepts, at least, a tuple argument, and returns another tuple formed from an arbitrary set of its elements? The conventional solution introduces the following simple variadic class template:

template <std::size_t ...Is>
struct indices {};

An object of type indices might then be created with, for example: indices<>; indices<0,2,4>; or indices<1,1,2,3,5,8>. Our select function may then be defined, as shown in the code below.

template <typename ...Ts, std::size_t ...Is>
auto
select(std::tuple<Ts...> t, indices<Is...>) ->
  decltype(std::make_tuple( std::get<Is...>(t)... )) {
  return   std::make_tuple( std::get<Is...>(t)... );
}

Calling select with the earlier tuple variable t1 and a indices<0,2,4> variable, again results in a tuple with type tuple<char,int,int>.

There are a few C++11 things to notice in this code. The Is template parameter pack is not expanded "directly" in the function body, due to the placement of the ellipsis. So, while indices<Is...>, say, would expand to indices<0,2,4>, in the select function above, the actual expansion becomes std::get<0>(t), std::get<2>(t), std::get<4>(t); three arguments for the variadic make_tuple function. Such ellipses will expand all parameter packs in the pattern to their left. Expanding multiple parameter packs of differing lengths, with a single ellipsis, will cause a compilation error.

Also worth noting: the use of C++11's trailing return type, and decltype specifier is, here, optional; the select function can be typed just as effectively by the more ornate code below. Often, however, the former typing technique is preferable as it has a simple, mechanical, syntax-based application; and so is generally applicable. With short functions the concise form can also provide a readable symmetry. With luck, perhaps by C++17, or maybe even C++14, we can do away with it altogether; after all, the auto keyword can bind to untyped lambda expressions.

template <typename ...Ts, std::size_t ...Is>
std::tuple<
  typename std::decay<
    typename std::tuple_element<Is,std::tuple<Ts...>>::type
  >::type...
>
select(std::tuple<Ts...> t, indices<Is...>) {
  return std::make_tuple( std::get<Is...>(t)... );
}

Finally, as only the template arguments of its type are used, the second function parameter is not bound to a name.

All well and good, but how would I modify every element of an arbitrary-length tuple? A common solution, seen here, here, and here, is to use make_indices, a variadic class template with a typedef member, type, which equates to an instantiation of the indices class template. The std::size_t template parameters of the indices type are instantiated as a zero-based finite arithmetic progression, with length equal to the number of template arguments given to make_indices. For example, make_indices<short,int>::type, would evaluate to indices<0,1>. The code below demonstrates a simple application of make_indices within a function template, id, which "does nothing"; well, it returns a tuple comprised of the same elements as the input. With additional parameters, make_indices can easily be used to create tuple versions of map and zipWith.

template <typename ...Ts>
std::tuple<Ts...> id(std::tuple<Ts...> t) {
  return select(t,typename make_indices<Ts...>::type());
}

Although useful, the make_indices class template has a number of weaknesses:

  • The template parameters of indices are fixed as std::size_t only;
  • The first index created is always 0;
  • The common difference between each index is fixed to 1;
  • The common difference is a positive value only;
  • make_indices can only be applied to type template parameter lists, and not non-type template parameters.

The first point can be addressed by a variadic, generic, index container:

template <typename T, T...>
struct indicesT {};

With tuples, the argument given to the relevant index function, std::get, will commonly have type std::size_t. The following type alias template allows the more straightforward std::size_t specialisation of indicesT to be used; e.g. indices<0,1,2> instead of indicesT<std::size_t,0,1,2>; also, the earlier definition of select can remain unchanged.

template <std::size_t ...Is>
using indices = indicesT<std::size_t, Is...>;

The traditional make_indices class template outlined earlier only allows us to specify the extent of the generated, zero-based, indices. Using the mk_index_range alias template, the same may be achieved using an integral range. For example, like make_indices<int,bool,char>::type, the type expression mk_index_range<0,2> will evaluate to indices<0,1,2>; or [0,2] in interval notation.

The mk_index_range alias template can also use a non-zero based start value; for example mk_index_range<8,10> will evaluate to indices<8,9,10>. A third, optional, template parameter of mk_index_range allows the specification of a stride. So, mk_index_range<1,9,2> will evaluate to indices<1,3,5,7,9>; and mk_index_range<9,1,-2> to indices<9,7,5,3,1>.

The indices produced by mk_index_range will always have type std::size_t; that is, the same type as the template parameter of the <tuple> function std::get. To produce signed indices, say of type int, a second alias template is provided: mk_index_rangei. Behind the scenes, something like mk_index_rangei<3,-3,-1>, which evaluates to indicesT<3,2,1,0,-1,-2,-3>, is defined as MkIndices<int,int,3,-3,-1>, using a more general alias template, MkIndices.

A fair question is, how many indices are produced by an arbitrary index range? For example, what is produced by mk_index_range<1,9,2> as opposed to mk_index_range<1,10,2>. How about mk_index_range<1,0,1>? The answer comes from the language of the new century: Fortran. With the loop-control of the DO construct defined by the grammar production below,

do-variable = expr1, expr2 [,expr3]

then the number of iterations is defined by the following equation:

niters = max((expr2 − expr1 + expr3)/expr3, 0)

The C++ code for this is a constexpr function which can be used within the template arguments of the mk_index_range implementation.

We're now in a position to have some fun. The following basic function, tuple_tail is used within the definition of the tuple overload of the insertion operator <<. The tuple_tail function returns a tuple comprised of all elements of the input tuple argument, minus the first element:

template <typename T, typename ...Ts>
tuple<Ts...>
tuple_tail(tuple<T,Ts...> t) {
  return select(t, mk_index_range<1,sizeof...(Ts)>());
}

The following function, tuple_reverse, unsurprisingly returns a tuple constructed from all the elements of the input tuple argument, in reverse order:

template <typename ...Ts>
tuple<Ts...>
tuple_reverse(tuple<Ts...> t) {
  return select(t, mk_index_range<sizeof...(Ts)-1,0,-1>());
}

The mk_index_range function template is now used throughout an updated version of the compile-time FFT code described in the previous post. The map, zipWith and iota functions there now all use mk_index_range; they're also similar to each other; and are interesting enough. The following function, condenseN, is though more compelling: returning a tuple comprised of every nth element of the input tuple. It is both integral to the FFT implementation; and uses a stride, or common difference, that isn't 1. Incidentally, the actual instantiation is condenseN<2>, and alas this will crash the current version of Clang; Clang 3.2 snapshot.

template<std::size_t N, typename ...Ts>
auto
condenseN(tuple<Ts...> t) ->
  decltype(select(t,mk_index_range<0,sizeof...(Ts)-1,N>())) {
  return   select(t,mk_index_range<0,sizeof...(Ts)-1,N>());
}

My personal favourite is also used by the compile-time FFT. The std::tuple_cat is a variadic function template which should catenate all tuples provided as arguments. The implementation below uses a helper function, tuple_cat_helper, which expands two parameter packs, Is and Js, within a single statement:

template <typename ...Ts>
tuple<>
tuple_cat() { return tuple<>(); }

template <typename ...Ts>
tuple<Ts...>
tuple_cat(tuple<Ts...> t) { return t; }

template <typename Tup1, typename Tup2, std::size_t ...Is, std::size_t ...Js>
auto tuple_cat_helper(Tup1 t1, Tup2 t2, indices<Is...>, indices<Js...>) ->
  decltype(make_tuple(get<Is>(t1)...,get<Js>(t2)...)) {
  return   make_tuple(get<Is>(t1)...,get<Js>(t2)...);
}

template <typename ...Ts, typename ...Us, typename ...Tups>
auto
tuple_cat(tuple<Ts...> t1, tuple<Us...> t2, Tups ...ts) ->
  decltype(tuple_cat(
             tuple_cat_helper(
               t1,t2,
               mk_index_range<0,sizeof...(Ts)-1>(),
               mk_index_range<0,sizeof...(Us)-1>()
             ),
             ts...
           )
          )
{
  return   tuple_cat(
             tuple_cat_helper(
               t1,t2,
               mk_index_range<0,sizeof...(Ts)-1>(),
               mk_index_range<0,sizeof...(Us)-1>()
             ),
             ts...
           );
}

Note that the C++11 standard definition of std::tuple is not defined as constexpr. The non-standard tuple implementation provided with the FFT code is contained within the ctup namespace.

The code for mk_index_range is here and the constexpr-friendly tuple implementation is here.