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

### December 3, 2012

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

**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**

`std::make_tuple`

**will be an**

`t1`

**.**

`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

**, a**

`std::get`

**, represents an index; and must be a constant expression. Using the**

`std::size_t`

**tuple from the code above,**

`t1`

**evaluates to an**

`std::get<4>(t1)`

**; with a value of**

`int`

**.**

`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,

**, having type**

`t3`

**, is formed from copies of the 1st, 3rd, and 5th elements from the earlier tuple,**

`tuple<char,int,int>`

**.**

`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**,

**, and**

`2`

**. How could we instead write a function template,**

`4`

*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<>`

**; or**

`indices<0,2,4>`

**. Our**

`indices<1,1,2,3,5,8>`

**function may then be defined, as shown in the code below.**

`select`

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

**and a**

`t1`

**variable, again results in a tuple with type**

`indices<0,2,4>`

**.**

`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

**, say, would expand to**

`indices<Is...>`

**, in the**

`indices<0,2,4>`

**function above, the actual expansion becomes**

`select`

**; three arguments for the variadic**

`std::get<0>(t), std::get<2>(t), std::get<4>(t)`

**function. Such ellipses will expand all parameter packs in the**

`make_tuple`

*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

**function**

`select`

*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

**keyword can bind to untyped lambda expressions.**

`auto`

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

**member,**

`typedef`

**, which equates to an instantiation of the**

`type`

**class template. The**

`indices`

**template parameters of the**

`std::size_t`

**type are instantiated as a zero-based finite arithmetic progression, with length equal to the number of template arguments given to**

`indices`

**. For example,**

`make_indices`

**, would evaluate to**

`make_indices<short,int>::type`

**. The code below demonstrates a simple application of**

`indices<0,1>`

**within a function template,**

`make_indices`

**, which “does nothing”; well, it returns a tuple comprised of the same elements as the input. With additional parameters,**

`id`

**can easily be used to create tuple versions of**

`make_indices`

*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
are fixed as`indices`

only;`std::size_t`

- 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;
can only be applied to type template parameter lists, and not non-type template parameters.`make_indices`

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

**. The following**

`std::size_t`

*type alias template*allows the more straightforward

**specialisation of**

`std::size_t`

**to be used; e.g.**

`indicesT`

**instead of**

`indices<0,1,2>`

**; also, the earlier definition of**

`indicesT<std::size_t,0,1,2>`

**can remain unchanged.**

`select`

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

**alias template, the same may be achieved using an integral range. For example, like**

`mk_index_range`

**, the type expression**

`make_indices<int,bool,char>::type`

**will evaluate to**

`mk_index_range<0,2>`

**; or**

`indices<0,1,2>`

**in interval notation.**

`[0,2]`

The ** mk_index_range** alias template can also use a non-zero based

*start*value; for example

**will evaluate to**

`mk_index_range<8,10>`

**. A third, optional, template parameter of**

`indices<8,9,10>`

**allows the specification of a**

`mk_index_range`

*stride*. So,

**will evaluate to**

`mk_index_range<1,9,2>`

**; and**

`indices<1,3,5,7,9>`

**.**

`mk_index_range<9,1,-2>`

The indices produced by ** mk_index_range** will always have type

**; that is, the same type as the template parameter of the**

`std::size_t`

**function**

`<tuple>`

**. To produce**

`std::get`

*signed*indices, say of type

**, a second alias template is provided:**

`int`

**. Behind the scenes, something like**

`mk_index_rangei`

**, which evaluates to**

`mk_index_rangei<3,-3,-1>`

**, is defined as**

`indicesT<3,2,1,0,-1,-2,-3>`

**, using a more general alias template,**

`MkIndices<int,int,3,-3,-1>`

**.**

`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

**. How about**

`mk_index_range<1,10,2>`

**? The answer comes from the language of the new century: Fortran. With the**

`mk_index_range<1,0,1>`

*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

**implementation.**

`mk_index_range`

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**

`<<`

**function returns a tuple comprised of all elements of the input tuple argument,**

`tuple_tail`

*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`

**and**

`zipWith`

**functions there now all use**

`iota`

**; they’re also similar to each other; and are interesting enough. The following function,**

`mk_index_range`

**, is though more compelling: returning a tuple comprised of every**

`condenseN`

*n*th element of the input tuple. It is both integral to the FFT implementation;

*and*uses a stride, or common difference, that isn’t

**. Incidentally, the actual instantiation is**

`1`

**, and alas this will crash the current version of Clang; Clang 3.2 snapshot.**

`condenseN<2>`

template <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,

**, which expands two parameter packs,**

`tuple_cat_helper`

**and**

`Is`

**, within a single statement:**

`Js`

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

**. The non-standard**

`constexpr`

**implementation provided with the FFT code is contained within the**

`tuple`

**namespace.**

`ctup`

The code for ** mk_index_range** is here and the

**-friendly**

`constexpr`

**implementation is here.**

`tuple`

December 3, 2012 at 12:07 pm

> the select function can be typed just as effectively by the more ornate code below.

This is not true. That code is not correct in the general case. As a start, that implementation of select is not the best, but ignoring that for a moment, the second version does not always behave like the first one.

The assertions in this program hold: http://stacked-crooked.com/view?id=2383053c85152e4695364e32ce1688df. That actually means the second version does not compile in the presence of tuples references: http://stacked-crooked.com/view?id=8b4471beb5cd06a55853a04e9a483f4c. And there are other behaviours of the first version that the second version does not emulate, namely those concerning std::reference_wrapper.

December 3, 2012 at 11:19 pm

Thankyou, you are correct. I’m not so interested in reference arguments here, so I’ve simply updated the return type of the non-

version to`decltype`

alsodecay (using) the tuple elements. I’m actually quite pleased that it’s now`std::decay`

moreverbose, as it emphasises my preference here for the use of. I’ve given stacked-crooked.com a whirl with my own test here.`decltype`