details of std::make_index_sequence and std::index_sequence
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 astypename indexSequenceHelper<3>::type
[N
is3
]indexSequenceHelper<3>
match only the general case so inherit fromindexSequenceHelper<2, 2>
[N
is3
andNext...
is empty]indexSequenceHelper<2, 2>
match only the general case so inherit fromindexSequenceHelper<1, 1, 2>
[N
is2
andNext...
is2
]indexSequenceHelper<1, 1, 2>
match only the general case so inherit fromindexSequenceHelper<0, 0, 1, 2>
[N
is1
andNext...
is1, 2
]indexSequenceHelper<0, 0, 1, 2>
match both cases (general an partial specialization) so the partial specialization is applied and definetype = indexSequence<0, 1, 2>
[Next...
is0, 1, 2
]
Conclusion: makeIndexSequence<3>
is indexSequence<0, 1, 2>
.
Hope this helps.
--- EDIT ---
Some clarifications:
std::index_sequence
andstd::make_index_sequence
are available starting from C++14my 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>
, usingmakeIndexSequence<1000>
you implement, in a recursive way, 1000 differentindexSequenceHelper
; 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.