Compile-time integer sequences

ISO/IEC JTC1 SC22 WG21 N3658 = 2013-04-18

Jonathan Wakely, cxx@kayari.org

Revision History
Introduction
Rationale and examples of use
    Piecewise construction of std::pair.
    Convert array to tuple
    N3466 more_perfect_forwarding_async example
Solution
    Type of integers in the sequence
    Non-consecutive integer sequences
    Members of integer sequences
    Efficiency considerations
Impact on standard
        20.x Compile-time integer sequences [intseq]
        20.x.1 In general [intseq.general]
        20.x.2 Class template integer_sequence [intseq.intseq]
        20.x.3 Alias template make_integer_sequence [intseq.make]
References

Revision History

N3658 Revision 1 (post-Bristol mailing)

N3493 Initial paper (Spring 2013 mid-term mailing)

Introduction

In a function template such as

template<class... T>
  void f(T... t);

performing some operation using every member of the parameter pack is as simple as expr(t...), because t can be used directly in a pack expansion. When the parameter pack appears as part of another type such as std::tuple, the function parameter is not a parameter pack so can't be expanded directly. For example, in the function template

template<class... T>
  void foo(std::tuple<T...> t);

performing an operation on every element of the tuple requires additional code because t is not a parameter pack and expr(t...) is not valid. (By comparison, in Python unpacking tuples to pass to variadic functions is built in to the language and is as convenient as func(*t) [Python].)

For unpacking a tuple in C++ the brute force alternative to expr(t...) is to instantiate a class template with a static member function, such as

DoExpr<0>::apply(t);

which calls

DoExpr<1>::apply(t, std::get<0>(t));

which calls

DoExpr<2>::apply(t, t0, std::get<1>(t));

and so on for each element until DoExpr<sizeof...(T)> is instantiated and can call expr(t0, t1, ..., tN). This requires the user to write a recursive class template (and a specialization to terminate the recursion) with a variadic member function template and to use perfect forwarding (not shown here) to avoid O(N2) copies. To make a generic, reusable solution that can apply an arbitrary function object to each element requires template partial specialization and is probably beyond the abilities of many users of std::tuple, so the alternative is to write non-generic code and then rewrite it slightly differently when a different operation on tuples is needed. This is a fairly complicated task and the end result is not even a very natural way to write the desired operation. The call to

DoExpr<0>::apply(t);

is far less expressive than something like expr(t...).

A simpler and more natural solution is to introduce a new parameter pack, I, consisting of integers [0,N] and then use it in a pack expansion such as expr(std::get<I>(t)...). This requires no recursion and no class template specializations. This proposal is to standardize a mechanism for creating a parameter pack containing an integer sequence.

Rationale and examples of use

The proposal is to add a type like

template<int...> struct index_sequence { };

so that an instantiation like index_sequence<0, 1, 2, 3> can be passed to a function template that deduces a parameter pack containing the integer sequence 0, 1, 2, 3.

In order to pass an index_sequence to a function it must be possible to construct the desired specialization either from the length of sequence desired or from a parameter pack from which the length can be deduced. This proposal offers both options, so that given the type tuple<T...> the sequence [0, sizeof...(T)) needed to expand the tuple can be created by using the alias make_index_sequence<sizeof...(T)> (or equivalently make_index_sequence<tuple_size<tuple<T...>>::value>) or by using the alias index_sequence_for<T...>.

With such a type in your toolbox it is easy to write the generic, reusable solution described above for expanding tuple elements as arguments to a function object:

template<typename F, typename Tuple, size_t... I>
  auto
  apply_(F&& f, Tuple&& args, index_sequence<I...>)
  -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(args))...))
  {
    return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(args))...);
  }

template<typename F, typename Tuple,
         typename Indices = make_index_sequence<std::tuple_size<Tuple>::value>>
  auto
  apply(F&& f, Tuple&& args)
  -> decltype(apply_(std::forward<F>(f), std::forward<Tuple>(args), Indices()))
  {
    return apply_(std::forward<F>(f), std::forward<Tuple>(args), Indices());
  }

This solution still uses recursion and template specialization, but only in the implementation of make_index_sequence, where users don't need to write or understand it. Standardizing the components makes it trivial for users to expand tuple-like types in any situation, including the examples below. A type like index_sequence is a good candidate for standardization, as similar types are already used in at least two major standard library implementations and have been reinvented often. Similar types feature in several answers to questions on sites such as Stack Overflow [Schaub] [Wakely] [Kühl], where the number of questions about unpacking tuples and the number of times types like index_sequence are used in answers demonstrates the demand for a solution to the problem.

Piecewise construction of std::pair.

Piecewise construction of std::pair requires two tuples of arguments to be expanded to form constructor arguments for the pair members. One implementation technique is to delegate to a private constructor for pair that takes two types like index_sequence, for example

template<class... Args1, class... Args2>
  pair(piecewise_construct_t, tuple<Args1...> args1, tuple<Args2...> args2)
    : pair(args1, args2, index_sequence_for<Args1...>{}, index_sequence_for<Args2...>{})
  { }

private:

template<class... A1, class... A2, size_t... I1, size_t... I2>
  pair(tuple<A1...>& a1, tuple<A2...>& a2, index_sequence<I1...>, index_sequence<I2...>)
    : first(std::get<I1>(std::move(a1))...),
      second(std::get<I2>(std::move(a2))...)
  { }

Convert array to tuple

A note in [tuple.creation] says that implementations might support using std::tuple_cat with other tuple-like type such as std::array, but it's not required. Users who need to implement it themselves can do so using a recursive template, using tuple_cat to build up a tuple element by element, but this creates lots of temporaries and instantiations. An implementation is shown here for comparison with the index_sequence solution:

template<typename T, std::size_t N, std::size_t I = 0>
  struct a2t_
  {
    static_assert( I < N, "index within array bound" );

    template<typename... Elts>
      static auto
      cat(std::tuple<Elts...>&& t, const std::array<T, N>& a)
      -> decltype(a2t_<T, N, I+1>::cat(std::tuple_cat(t, std::make_tuple(a[I])), a))
      {
          return a2t_<T, N, I+1>::cat(std::tuple_cat(t, std::make_tuple(a[I])), a);
      }
  };

template<typename T, std::size_t N>
  struct a2t_<T, N, N>
  {
    template<typename... Elts>
      static std::tuple<Elts...>
      cat(std::tuple<Elts...>&& t, const std::array<T, N>& a)
      {
          return t;
      }
  };

template<typename T, std::size_t N>
  auto
  a2t(const std::array<T, N>& a)
  -> decltype(a2t_<T, N>::cat(std::tuple<>(), a))
  {
    return a2t_<T, N>::cat(std::tuple<>(), a);
  }

Using index_sequence the implementation is almost trivial:

template<typename Array, size_t... I>
  auto
  a2t_(const Array& a, index_sequence<I...>)
    -> decltype(std::make_tuple(a[I]...))
  {
    return std::make_tuple(a[I]...);
  }

template<typename T, std::size_t N, typename Indices = make_index_sequence<N>>
  auto
  a2t(const std::array<T, N>& a)
    -> decltype(a2t_(a, Indices()))
  {
    return a2t_(a, Indices());
  }

N3466 more_perfect_forwarding_async example

The more_perfect_forwarding_async example in N3466 refers to a "complicated template metafunction" [DRayX] which can be replaced with the comparatively simple apply() function template defined above.

Solution

While I hope there will be broad agreement that some form of integer sequence template should be standardized there are some parts of the solution which might be harder to agree on. The changes to the working paper proposed below are my preferred solution but the specific details are less important than getting some kind of template that makes it easy to solve the problems described above.

Type of integers in the sequence

It's not obvious to me what type of integer should be used in the parameter pack of the class template. The natural type for indexing into tuples and arrays is std::size_t, but that type has a far larger range of values than needed. I consider it unlikely that any compiler will support parameter packs that can accept SIZE_MAX arguments for the foreseeable future. Another question is whether the integer type should be signed or unsigned. Indices are naturally unsigned, but there could be other interesting uses for integer sequences other than unpacking tuples and arrays which would be more difficult if the values cannot be negative. Conversely there might be valid use cases where the wrapping behaviour of unsigned integers is preferable to worrying about overflow.

The proposed solution is to define a generic integer_sequence class template which can be instantiated as integer_sequence<int> or integer_sequence<unsigned char> or any other integer type. By using alias templates to denote specializations for common types it is just as convenient to use the generic template as it would be if it wasn't parameterized by the integer type, for instance the examples above work equally well whether index_sequence<I...> is a specialization of a class template or an alias for integer_sequence<size_t, I...>.

Non-consecutive integer sequences

There is no reason to restrict the values in an integer sequence to consecutive integers starting from zero. It is very simple to transform index_sequence<I...> to index_sequence<I+n...> or index_sequence<I*n...>. Such sequences would be useful to access only the even elements of an array, for example, but such transformations are not necessary for the main purpose of unpacking tuples. If the standard provides the integer_sequence type and simple metafunctions for generating basic sequences users can more easily create custom sequences.

Members of integer sequences

For most uses

template<int...> struct index_sequence { };

is sufficient, but it's simple to define type and size members describing the type and to provide append and next members for extending sequences, as shown in the proposed changes below.

These members are not essential to the proposal and the suggestion might be due to my own bias as the next member is used by my implementation of the proposed changes below [integer_seq] i.e. in the unspecified details of how make_integer_sequence works.

Efficiency considerations

For a sequence of N integers the reference implementation recursively instantiates N templates, limiting the length of sequences to (at most) the instantiation depth of the compiler. It is quite easy to reduce the number of instantiations to log2(N) by starting at both ends of the sequence and working inwards to meet the middle.

A compiler intrinisic could be used to instantiate an arbitrary-length integer_sequence with no recursion.

There have been suggestions of a core feature that would define ...3 as the parameter pack {0, 1, 2, 3}, which would provide an alternative way to solve the problems solved by this proposal. This language feature will not be in C++14 if accepted at all, so should not prevent solving the problem now.

Impact on standard

This is a pure addition to the library. It is expected that implementations would be able to replace existing equivalent code with uses of integer_sequence if desired.

Add to the synopsis in [utility] paragraph 2, after the declaration of tuple:


// 20.x Compile-time integer sequences

template<class T, T...> struct integer_sequence;
template<size_t... I>
  using index_sequence = integer_sequence<size_t, I...>;

template<class T, T N>
  using make_integer_sequence = integer_sequence<T, see below>;
template<size_t N>
  using make_index_sequence = make_integer_sequence<size_t, N>;

template<class... T>
  using index_sequence_for = make_index_sequence<sizeof...(T)>;

Add a new subclause after [pairs]:

20.x Compile-time integer sequences [intseq]

20.x.1 In general [intseq.general]

The library provides a class template that can represent an integer sequence. When used as an argument to a function template the parameter pack defining the sequence can be deduced and used in a pack expansion.

[Example:

template<class F, class Tuple, std::size_t... I>
  auto
  apply_impl(F&& f, Tuple&& t, index_sequence<I...>)
  -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)
  {
    return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
  }

template<class F, class Tuple, class Indices
         = make_index_sequence<std::tuple_size<Tuple>::value>>
  auto
  apply(F&& f, Tuple&& t)
  -> decltype(apply_impl(std::forward<F>(f), std::forward<Tuple>(t), Indices()))
  {
    return apply_impl(std::forward<F>(f), std::forward<Tuple>(t), Indices());
  }

— end example ]

20.x.2 Class template integer_sequence [intseq.intseq]


namespace std {
  template<class T, T... I>
  struct integer_sequence {
    typedef T value_type;

    static constexpr size_t size() noexcept { return sizeof...(I); }
  };
}  // namespace std

T shall be an integer type.

20.x.3 Alias template make_integer_sequence [intseq.make]


template<class T, T N>
  using make_integer_sequence = integer_sequence<T, see below>;

If N is negative the program is ill-formed. The alias template make_integer_sequence denotes a specialization of integer_sequence with N template non-type arguments. The type make_integer_sequence<T, N> denotes the type integer_sequence<T, 0, 1, ..., N-1>. [ Note: make_integer_sequence<int, 0> denotes the type integer_sequence<int> — end note ]

References

[Python]
Python, The Python Tutorial, 10 January 2013, Unpacking Argument Lists, http://docs.python.org/dev/tutorial/controlflow.html#unpacking-argument-lists
[Schaub]
Johannes Schaub, "unpacking" a tuple to call a matching function pointer, 22 October 2011, http://stackoverflow.com/a/7858971
[Wakely]
Jonathan Wakely, Variadic templates: iterate over type/template argument, 27 December 2012, http://stackoverflow.com/a/11196263
[Kühl]
Dietmar Kühl, How to guarantee order of argument evaluation when calling a function object?, 27 December 2012, http://stackoverflow.com/a/14059084
[DRayX]
DRayX, How do I expand a tuple into variadic template function's arguments?, 29 September 2012, http://stackoverflow.com/a/12650100
[integer_seq]
Jonathan Wakely, integer_seq, 10 January 2013, <integer_seq.h>, https://gitorious.org/redistd/integer_seq/blobs/master/integer_seq.h