details of std::make_index_sequence and std::index_sequence

Question

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 :)

Berkow

Answer 1

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.

Direful

A good answer, but I would add there's a reason some implementations you might find are quite a bit more complicated: they attempt to reduce the number and/or depth of template instantiations, because there can be a compiler limit to the depth of recursive instantiations, and reducing the total number could make compile times faster. – Duffie

THANK you! Thats great. Exactly what I was after. – Berkow

@Duffie - I know, I know... I usually (in C++11) use a different implementation with logarithmic complexity. But my intention was make it simple to understand. Maybe I'll try to explain this point a little better... – Direful

@Direful Yes, this simple explanation is definitely more appropriate to the question. Just suggesting some extra info. – Duffie

@Berkow - added a couple of clarifications (see also the aschepler's comment). – Direful

@Duffie - I've tried (but the problem is that I know C++ better than english; I don't know if is comprehensible) – Direful

Answer 2

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.

Flathead

Interesting... yes, with if constexpr become simpler. But you should precise that if constexpr is available starting from C++17. – Direful

Answer 3

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>());

Eyre

can you please add some explanation to the above implementation? It appears to recurse with log(N) depth. – Admit

it's based on doubling the amount of indices, if possible, so it finishes pretty quick. – Eyre

This was very helpful to write a reverse index sequence. – Deportment