## Implementation C++14 make_integer_sequence

Here's a `log N`

implementation that doesn't even need an increased max-depth for template instantiations and compiles pretty fast:

`// using aliases for cleaner syntax`

template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>

struct concat<seq<I1...>, seq<I2...>>

: seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>

using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;

template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>

struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};

template<> struct gen_seq<1> : seq<0>{};

## How to understand libcxx's implementation of make_integer_sequence?

You also need to understand `__repeat`

to see how this works:

`template<typename _Tp, size_t ..._Extra> struct __repeat;`

template<typename _Tp, _Tp ..._Np, size_t ..._Extra> struct __repeat<integer_sequence<_Tp, _Np...>, _Extra...> {

typedef integer_sequence<_Tp,

_Np...,

sizeof...(_Np) + _Np...,

2 * sizeof...(_Np) + _Np...,

3 * sizeof...(_Np) + _Np...,

4 * sizeof...(_Np) + _Np...,

5 * sizeof...(_Np) + _Np...,

6 * sizeof...(_Np) + _Np...,

7 * sizeof...(_Np) + _Np...,

_Extra...> type;

}

It takes two template parementers: An integer sequence and a paremeter pack of `_Extra`

values.

It has a member typedef `type`

that is an integer sequence of the same type as the initial integer sequence.

It's members are as follows:

`_Np..., // The original values`

sizeof...(_Np) + _Np...,

// sizeof...(_Np) is the number of integers in the sequence. This is a fold expression

// that adds the sizeof...(_Np) to every integer.

// So (_Np..., sizeof...(_Np) + _Np...) for <0, 1, 2> would be

// (<0, 1, 2>..., <3 + 0, 3 + 1, 3 + 2>...), which is `<0, 1, 2, 3, 4, 5>`.

// The rest of the lines are the same, but starting with a different

// multiple of sizeof...(_Np)

// `<0, 1, ..., N>` into an integer sequence of `<0, 1, ..., 8N>`.

_Extra...

// And then add `_Extra` to the end

`__make<_Np>`

from `_Np = 0`

to `_Np = 7`

is hard coded. Otherwise, it uses `__parity`

as a helper type.

This will use `__repeat`

to repeat `__make<_Np / 8>`

8 times, creating the desired length, and then add the remaining items using extra based on how much bigger it is than the last multiple of 8 (Called "parity" here) as `_Extra`

.

It's not so much "manually unrolling the loop". It's just recursively dividing `make_integer_sequence<N>`

into `repeat_8_times<make_integer_sequence<N / 8>> /* + remainder */`

, so it's "recursion with a base case"

## How exactly is std::make_integer_sequence implemented?

None of the major compiler standard libraries currently provide a sub-O(n) (logarithmic or otherwise) implementation of N3658 compile-time integer sequences.

### libstdc++ (gcc):

Standard O(n) implementation walking a chain of `typedef`

s. This is equivalent to a FP function concatenating to the end of a list returned by the recursive invocation.

### libc++ (clang):

O(n) implementation, but with an interesting 8x unrolled loop.

### MSVC (VS14 CTP1):

O(n), using recursive inheritance templated on an integral constant and integer sequence, the latter used as an accumulator (in the FP sense). (Note that the the VS14 implementation is actually located in the `type_traits`

header, not in `utility`

.)

ICC is not currently documented as providing compile-time integer constant support.

Worrying over the efficiency of `std::integer_sequence`

is probably not worth it at this point; any problem for which compile-time integer sequences are suited is going to bump up against the limits of compilers (in terms of numbers of function and template arguments, etc.) long before the big-O performance of the algorithm used influences compile times. Consider also that if `std::make_integer_sequence`

is used anywhere else in your compilation (e.g. in library template code) then the compiler will be able to reuse that invocation, as template metaprogramming is purely functional.

## 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++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>`

, 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 does integer_sequence get unfolded to generate a sequence?

The call to `make_inc_array<10>()`

returns `make_inc_array_impl(std::make_integer_sequence<int, 10>{})`

. `std::make_integer_sequence`

is an alias template. In particular, it's implemented so that `std::make_integer_sequence<int, 10>`

is an alias for the type `std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>`

. Thus, when `make_inc_array_impl`

is called with an argument of this type, `Is...`

gets deduced to `0 1 2 3 4 5 6 7 8 9`

in order to make the parameter type `std::integer_sequence<int, Is...>`

equal to the argument type. Finally, this pack is expanded in the body of `make_inc_array_impl`

. The pack expansion is guaranteed to occur in order, so it becomes `0 + 1`

, `1 + 1`

, ..., `9 + 1`

.

The most tricky part of this is `std::make_integer_sequence`

. How does it expand to an `std::integer_sequence`

specialization with the actual consecutive integers desired? Well, this was inserted into the standard library so that you don't have to remember how to do it yourself, but if you want to see the answer, look here.

You generally need a helper function which is invoked with the result of `std::make_integer_sequence<int, N>{}`

so that there is a place to put the individual integers in the sequence, *i.e.,* the pack `Is...`

. Now that you're aware of this trick, you'll start seeing many places where you can use it.

## Creating an index_sequence of N zeros

I suggest a `zero_sequence`

completely different: not a `struct`

but a `using`

based over a `decltype()`

, a `std::declval()`

and a only declared helper function (following the `std::declval()`

example.

I mean... if you define the following helper function

`template <std::size_t ... Is>`

constexpr auto zeHelper (index_sequence<Is...> const &)

-> decltype( index_sequence<(Is,0u)...>{} );

`zero_sequence`

can be defined as

`template <typename T>`

using zero_sequence = decltype(zeHelper(std::declval<T>()));

and you can declate both `a0`

and `b0`

`A0 a0; `

B0 b0; // now works

and compile without problems also

`static_assert( std::is_same<A0, B0>::value, "!" );`

I'm perplexed as to why this is happening [...] I don't understand why the two cases are different

The problem with your `zero_sequence`

template struct specialization

`template<size_t...I> `

struct zero_sequence<index_sequence<I...>> : index_sequence<(I*0u)...>{};

is that there is also the generic version (unimplemented, but there is)

`template<typename> struct zero_sequence;`

So when you use a `index_sequence`

as template parameter for `zero_sequence`

, the implemented specialization matches and is selected.

But when you use a `make_index_sequence`

, that inherit from `index_sequence`

and can be converted to a `index_sequence`

but isn't exactly a `index_sequence`

, the specialization doesn't match and the generic (unimplemented) version of `zero_sequence`

is selected.

Passing through a function, the `zeHelper()`

that I propose or something similar, avoids this problem because a `make_index_sequence`

is convertible to a `index_sequence`

.

## conversion error from make_integer_sequence to integer_sequence

I admit, I do not understand the error message. The reason the second version compiles but not the first is that template parameters cannot be deduced from default arguments but from function parameters. Consider this simpler example:

`#include <utility>`

#include <iostream>

template <unsigned int>

struct foo {};

template <unsigned int x>

foo<x> make_foo(){ return {};}

template <unsigned int x>

unsigned int f(foo<x> = make_foo<4>())

{

return 42;

}

int main()

{

std::cout << f() << std::endl;

return 0;

}

Here the error is a little more descriptive:

`<source>: In function 'int main()':`

<source>:18:18: error: no matching function for call to 'f()'

18 | std::cout << f() << std::endl;

| ^

<source>:11:14: note: candidate: 'template<unsigned int x> unsigned int f(foo<x>)'

11 | unsigned int f(foo<x> = make_foo<4>())

| ^

<source>:11:14: note: template argument deduction/substitution failed:

<source>:18:18: note: couldn't deduce template parameter 'x'

18 | std::cout << f() << std::endl;

| ^

The main purpose of `make_integer_sequence<unsigned int,N>`

is to make the transition from a single `N`

to the pack in `std::integer_sequence<unsigned int, I...>`

as you do it in your second example.

With a level of indirection you avoid that the caller must pass the parameter:

`// ...`

template <unsigned int... I>

unsigned int f(std::integer_sequence<unsigned int, I...>)

{

return (g<I>() + ...);

}

template <unsigned int X = N>

unsigned int f_wrap()

{

return f(std::make_integer_sequence<unsigned int,N>{});

}

int main()

{

std::cout << f_wrap() << std::endl;

return 0;

}

Live Demo

## Unexpanded parameter pack in function signature

No, this is not possible. `__integer_pack`

is not a function, it is a placeholder that is expanded by the compiler into a parameter pack. This is not something you can replicate within the language.

You can look at how gcc implements replacing the call to `__integer_pack`

with its expansion in gcc/cp/pt.c, starting at line 3750 currently. `builtin_pack_fn_p()`

identifies calls to `__integer_pack`

(the `_p`

suffix means "predicate"), and `expand_integer_pack`

performs the expansion.

You will need to write your own implementation (or copy an existing one) within the language.

## Compile-time generate integer sequence with one left out

You may use the following:

`#if 1 // Not in C++11 // make_index_sequence`

#include <cstdint>

template <std::size_t...> struct index_sequence {};

template <std::size_t N, std::size_t... Is>

struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {};

template <std::size_t... Is>

struct make_index_sequence<0u, Is...> : index_sequence<Is...> { using type = index_sequence<Is...>; };

#endif // make_index_sequence

namespace detail

{

template <typename Seq1, std::size_t Offset, typename Seq2> struct concat_seq;

template <std::size_t ... Is1, std::size_t Offset, std::size_t ... Is2>

struct concat_seq<index_sequence<Is1...>, Offset, index_sequence<Is2...>>

{

using type = index_sequence<Is1..., (Offset + Is2)...>;

};

}

template <std::size_t N, std::size_t E>

using gen_seq = typename detail::concat_seq<typename make_index_sequence<E>::type, E + 1, typename make_index_sequence<(N > E) ? (N - E - 1) : 0>::type>::type;

static_assert(std::is_same<index_sequence<0, 1, 3, 4>, gen_seq<5, 2>>::value, "");

static_assert(std::is_same<index_sequence<1, 2>, gen_seq<3, 0>>::value, "");

static_assert(std::is_same<index_sequence<0, 1, 2, 3>, gen_seq<4, 4>>::value, "");

Live example

## Expand std::vector into parameter pack

It's possible, as long as you provide an upper bound to the number of arguments.

Using Xeo's implementation of `std::index_sequence`

for C++11:

`template <unsigned... Idx>`

void trampoline(const std::vector<int>& vElements, seq<Idx...>) {

return DoStuff(vElements[Idx]...);

}

template <std::size_t Arity>

void trampoline(const std::vector<int>& vElements) {

return trampoline(vElements, typename gen_seq<Arity>::seq{});

}

template <unsigned... Idx>

void CallDoStuff(const std::vector<int>& vElements, seq<Idx...>) {

using trampoline_t = void (*)(const std::vector<int>&);

constexpr trampoline_t trampolines[]{

trampoline<Idx>...

};

trampolines[vElements.size()](vElements);

}

template <std::size_t Max>

void CallDoStuff(const std::vector<int>& vElements) {

assert(vElements.size() <= Max);

return CallDoStuff(vElements, typename gen_seq<Max + 1>::seq{});

}

See it live on Wandbox

### Related Topics

How Approximation Search Works

Why Should the Implementation and the Declaration of a Template Class Be in the Same Header File

Difference Between the Dot (.) Operator and -≫ in C++

Function With Same Name But Different Signature in Derived Class

How to See a C/C++ Source File After Preprocessing in Visual Studio

How Does Dereferencing of a Function Pointer Happen

Subclass/Inherit Standard Containers

Are Std::Vector Elements Guaranteed to Be Contiguous

Printing the Correct Number of Decimal Points With Cout

Why Is Address of Char Data Not Displayed

Why C++11 In-Class Initializer Cannot Use Parentheses

When Should I Use the New Keyword in C++

Recursive Function That Returns All Substrings of a String

Why Would We Call Cin.Clear() and Cin.Ignore() After Reading Input