details of std::make_index_sequence and std::index_sequence

I'm enjoying ramping up on variadic templates and have started fiddling about with this new feature. I'm trying to get my head around the implementation details of std::index_sequence's (used for tuple implementation). I see sample code around there, but I really want a dumbed down step by step explanation of how an std::index_sequence is coded and the meta programming principal in question for each stage. Think really dumbed down :)

3 Answers

I see sample code around there, but I really want a dumbed down step by step explanation of how an index_sequence is coded and the meta programming principal in question for each stage.

What you ask isn't exactly trivial to explain...

Well... std::index_sequence itself is very simple: is defined as follows

template<std::size_t... Ints> using index_sequence = std::integer_sequence<std::size_t, Ints...>; 

that, substantially, is a template container for unsigned integer.

The tricky part is the implementation of std::make_index_sequence. That is: the tricky part is pass from std::make_index_sequence<N> to std::index_sequence<0, 1, 2, ..., N-1>.

I propose you a possible implementation (not a great implementation but simple (I hope) to understand) and I'll try to explain how it works.

Non exactly the standard index sequence, that pass from std::integer_sequence, but fixing the std::size_t type you can get a reasonable indexSequence/makeIndexSequence pair with the following code.

// index sequence only template <std::size_t ...> struct indexSequence { }; template <std::size_t N, std::size_t ... Next> struct indexSequenceHelper : public indexSequenceHelper<N-1U, N-1U, Next...> { }; template <std::size_t ... Next> struct indexSequenceHelper<0U, Next ... > { using type = indexSequence<Next ... >; }; template <std::size_t N> using makeIndexSequence = typename indexSequenceHelper<N>::type; 

I suppose that a good way to understand how it works is follows a practical example.

We can see, point to point, how makeIndexSequence<3> become index_sequenxe<0, 1, 2>.

• We have that makeIndexSequence<3> is defined as typename indexSequenceHelper<3>::type [N is 3]

• indexSequenceHelper<3> match only the general case so inherit from indexSequenceHelper<2, 2> [N is 3 and Next... is empty]

• indexSequenceHelper<2, 2> match only the general case so inherit from indexSequenceHelper<1, 1, 2> [N is 2 and Next... is 2]

• indexSequenceHelper<1, 1, 2> match only the general case so inherit from indexSequenceHelper<0, 0, 1, 2> [N is 1 and Next... is 1, 2]

• indexSequenceHelper<0, 0, 1, 2> match both cases (general an partial specialization) so the partial specialization is applied and define type = indexSequence<0, 1, 2> [Next... is 0, 1, 2]

Conclusion: makeIndexSequence<3> is indexSequence<0, 1, 2>.

Hope this helps.

--- EDIT ---

Some clarifications:

• std::index_sequence and std::make_index_sequence are available starting from C++14

• my example is simple (I hope) to understand but (as pointed by aschepler) has the great limit that is a linear implementation; I mean: if you need index_sequence<0, 1, ... 999>, using makeIndexSequence<1000> you implement, in a recursive way, 1000 different indexSequenceHelper; but there is a recursion limit (compiler form compiler different) that can be less than 1000; there are other algorithms that limits the number of recursions but are more complicated to explain.

For the sake of completeness, I'll add a more modern implementation of std::make_index_sequence, using if constexpr and auto, that make template programming a lot more like "normal" programming.

template <std::size_t... Ns> struct index_sequence {}; template <std::size_t N, std::size_t... Is> auto make_index_sequence_impl() { // only one branch is considered. The other may be ill-formed if constexpr (N == 0) return index_sequence<Is...>(); // end case else return make_index_sequence_impl<N-1, N-1, Is...>(); // recursion } template <std::size_t N> using make_index_sequence = std::decay_t<decltype(make_index_sequence_impl<N>())>; 

I strongly advise to use this style of template programming, which is easier to reason about.

Lest it be forgotten:

template <std::size_t N, std::size_t ...I> constexpr auto make_index_sequence_impl() noexcept { if constexpr (!N) { return std::index_sequence<I...>(); } else if constexpr (!sizeof...(I)) { return make_index_sequence_impl<N - 1, 0>(); } else if constexpr (N >= sizeof...(I)) { return make_index_sequence_impl<N - sizeof...(I), I..., sizeof...(I) + I...>(); } else { return []<auto ...J>(std::index_sequence<J...>) noexcept { return std::index_sequence<I..., sizeof...(I) + J...>(); }(make_index_sequence_impl<N>()); // index concatenation } } template <size_t N> using make_index_sequence = decltype(make_index_sequence_impl<N>());