Details of Std::Make_Index_Sequence and Std::Index_Sequence

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

How do I reverse the order of the integers in a `std::integer_sequenceint, 4, -5, 7, -3`?

A solution that doesn't use std::tuple is to convert to an std::array and access the corresponding indices with the help of std::make_index_sequence.

namespace detail {
    template<typename T, T... N, std::size_t... Indices>
    constexpr auto reverse_sequence_helper(std::integer_sequence<T, N...> sequence,
                                           std::index_sequence<Indices...>) {
        constexpr auto array = std::array<T, sizeof...(N)> { N... };
        return std::integer_sequence<T, array[sizeof...(Indices) - Indices - 1]...>();
    }
}
template<typename T, T... N>
constexpr auto reverse_sequence(std::integer_sequence<T, N...> sequence) {
    return detail::reverse_sequence_helper(sequence,
                                           std::make_index_sequence<sizeof...(N)>());
}

---

if C++20 is available, it can be reduced to this function with the help of templated lambdas:

template<typename T, T... N>
constexpr auto reverse_sequence(std::integer_sequence<T, N...> sequence) {
    constexpr auto array = std::array { N... };
 
    auto make_sequence = [&]<typename I, I... Indices>(std::index_sequence<Indices...>) {
        return std::integer_sequence<T, array[sizeof...(Indices) - Indices - 1]...>();
    };
    return make_sequence(std::make_index_sequence<sizeof...(N)>());
}

Making an index sequence tuple

pass a sequence of ints 0, 1, 2, 3, ..., 99 to [function arguments]

You don't need tuples. Do this:

template <std::size_t ...I>
void foo(std::index_sequence<I...>)
{
    format("foo", I...);
}

int main()
{
    foo(std::make_index_sequence<42>());
}

---

If you insist on std::apply, it understands std::array out of the box. You just need to handle the first parameter separately, since it's not an int.

const int n = 32;
std::array<int, n> array;
for (int i = 0; i < n; i++)
    array[i] = i;
std::apply([](auto ...params){format("foo", params...);}, array);

---

For educational purposes, here's the answer to the original question. This is how you make a tuple:

template <typename T, typename I>
struct n_tuple_helper {};

template <typename T, std::size_t ...I>
struct n_tuple_helper<T, std::index_sequence<I...>>
{
    using type = std::tuple<std::enable_if_t<I || true, T>...>;
};

template <typename T, std::size_t N>
using n_tuple = typename n_tuple_helper<T, std::make_index_sequence<N>>::type;

Now, n_tuple<int, 3> expands to std::tuple<int, int, int>

Creating a structure with an expanded index sequence

You can move the expansion entirely inside the class:

template<typename T, std::size_t N>
struct vec
{
public:
    T e[N];
    vec() : e{} {}
    explicit vec(const T& s) : vec{s, std::make_index_sequence<N>{}} {}
private:
    template <std::size_t ... Is>
    vec(const T& s, std::index_sequence<Is...>) : e{(Is, s)...} {}
};

how does the make_index_sequence work?

Let's play compiler, and substitute values for template parameters

When it encounters a type like std::make_index_sequence<3>, it goes and looks at the template and it's specialisations, and matches to

template <3>
struct make_index_sequence : public make_index_sequence<2, 2> {};

The base class of make_index_sequence<3> is another instantiation of make_index_sequence, so we repeat with new parameters

template <2, 2>
struct make_index_sequence : public make_index_sequence<1, 1, 2> {};

And again

template <1, 1, 2>
struct make_index_sequence : public make_index_sequence<0, 0, 1, 2> {};

Now we reach the specialisation

template <0, 1, 2>
struct make_index_sequence<0, 0, 1, 2> : public index_sequence<0, 1, 2> {};

Now we have a type that is inherited (indirectly) from index_sequence<0, 1, 2>, so template functions can bind a parameter pack to the 0, 1, 2 to match the arguments passed.

sizeof...(T) is just an operator to count the size of the parameter pack T, so we have things like:

template <int, bool, char>
/* ... */ do_foo(std::tuple<int, bool, char> & ts)
{
    return do_foo_helper(ts, make_index_sequence<3>());
}

Which calls

template <int, bool, char, 0, 1, 2>
/* ... */ do_foo_helper(std::tuple<int, bool, char> & ts, std::index_sequence<0, 1, 2>)
{
    std::tie(foo(std::get<0>(ts)), foo(std::get<1>(ts)), foo(std::get<2>(ts)));
}

I.e. we only need the type of the second argument, not it's value (There's only one value of type std::index_sequence<0, 1, 2> anyway, it has no data members).

How to expand multiple index_sequence parameter packs to initialize 2d array in C++?

I think the problem comes from the fact that RowIs and ColIs are expanded at the same time, i.e. both always having the same values during the initialization: 0, 1, 2...

You can check here that your current output (after fixing the compiler error) would be something like
[[1.1, 5.5, 9.9], [0, 0, 0], [0, 0, 0]] for the matrix below:

Matrix<3, 3> m{
    { 1.1, 2.2, 3.3 },
    { 4.4, 5.5, 6.6 },
    { 7.7, 8.8, 9.9 }
};

Because you only read fromil[0,0], il[1,1], and il[2,2] in order to set values_.

---

What you could do is to create a sequence with a flat index, from 0 to Rows*Cols - 1, and read every value from il with FlatIs/Cols and FlatIs%Cols:

[Demo]

#include <array>
#include <cstdint>
#include <fmt/ranges.h>
#include <initializer_list>
#include <utility>

template<std::size_t Rows, std::size_t Cols>
class Matrix {
public:
    Matrix(std::initializer_list<std::initializer_list<float>> il)
        : Matrix(il, std::make_index_sequence<Rows*Cols>())
    {}

private:
    template<std::size_t... FlatIs>
    Matrix(std::initializer_list<std::initializer_list<float>> il,
        std::index_sequence<FlatIs...>)
        : values_{il.begin()[FlatIs/Cols].begin()[FlatIs%Cols]...}
    {}

public:
    std::array<std::array<float, Cols>, Rows> values_;
};

int main() {
    Matrix<4, 3> m{
        { 1.1, 2.2, 3.3 },
        { 4.4, 5.5, 6.6 },
        { 7.7, 8.8, 9.9 },
        { 3.1, 4.1, 5.9 }
    };
    fmt::print("{}", m.values_);
}

// Outputs:
//
//   [[1.1, 2.2, 3.3], [4.4, 5.5, 6.6], [7.7, 8.8, 9.9], [3.1, 4.1, 5.9]]

Empty braces around std::make_index_sequence

The first instance (std::make_index_sequence<N>) is used in a template argument list. It's only saying that the template type parameter Indices defaults to the type std::make_index_sequence<N>. No instances of anything are created there, the use is declarative.

The second instance (std::make_index_sequence<Size>{}) is creating a default constructed instance of that type. The {} are the new C++ syntax for initialization. When the braces are empty the object will be default constructed.

using std::index_sequence to initialize POD struct container with fixed size array members

if you want the output following output given HELLO

 Element:[H], Element:[E], Element:[L], Element:[L], Element:[O],

this code will work, although there will be an element for the null character if you pass a null terminated string.

#include <iostream>
#include <tuple>

#define MAX_NAME_CHARS 9
#define MAX_CONTAINER_SIZE 100

struct Element {
    char name[MAX_NAME_CHARS];
    bool bFlag;
    int foo;
    friend std::ostream& operator << (std::ostream& os, const Element& next) {
        os << next.name;
        return os;
    }    
};

struct Container {
    int entries;
    Element elems[MAX_CONTAINER_SIZE];    
    friend std::ostream& operator << (std::ostream& os, const Container& next) {        
            os << "Container: entries(" << next.entries << ")[";
            for (auto i = 0; i<next.entries; ++i) {
                os << next.elems[i] << ",";
            }
            os << "]\n";
            return os;
    } 
};

template<std::size_t N, std::size_t ... I>
constexpr Container makeContainerInSingle(const char(&singlecharnames)[N],
                                 std::index_sequence<I...>) {
    auto result = Container {
        N,
        {Element{
            {singlecharnames[I]},
            true, 
            0}...
        }
    };
    return result;
}

template<std::size_t N>
constexpr Container makeContainerSingle(const char(&singlecharnames)[N]) {
    return makeContainerInSingle(singlecharnames, std::make_index_sequence<N>{});
}

int main() {
    auto c2 = makeContainerSingle("HELLO");
    std::cout << c2 << std::endl;
}

output is the following

Container: entries(6)[H,E,L,L,O,,]

as an additional note, im not sure what, if anything, can be done to simplify the pattern using std::index_sequence although the index sequence can be constructed directly as in my example code if you consider that more simple.

---

Related Topics