Implementation C++14 Make_Integer_Sequence

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