## Intro

We’ll be discussing a mechanism that can, during compilation, generate a sequence [0, N] given an integer N. So for example, the following mappings can be generated :

int_seq<3> -> { 0, 1, 2, 3 } int_seq<2> -> { 0, 1, 2 } int_seq<1> -> { 0, 1 } int_seq<0> -> { 0 }

We choose to use a closed interval in the examples so that the last case won’t produce an empty set (and an awkward compilation).

## Know why

Being a compile time thing, this sequence can be embeeded in type information or used in contexts that demand compile time constants. Typical examples include :

**Filling a braced initializer list**. This has numerous uses, consider eg:template<N> void fU() { // int_seq<N> would come in handy here int N[] = { 0, 1 ... N-1, N }; }

**Pack expansion contexts**; more on this on the next post, but for now just consider getting all tuple elements when all you know is its size and*get<>*demands a compile time constant.- In
**complex compile time computations**(I’ll be posting about a compile time sqrt function, stay tuned)

## Know how

We present an implementation based on [3] tweaked to provide the closed interval :

// a sequence container ------------------------- template<int ...> struct ints { }; // integer sequence ----------------------------- template<int N, int... Is> struct int_seq : int_seq<N - 1, N, Is...> { }; template<int... Is> struct int_seq<0, Is...> { using type = ints<0, Is...>; }; // convenience alias ----------------------------- template<int N> using IS = typename int_seq<N>::type;

What happens here is that *int_seq* inherits from “another version” of itself; Inheriting from an incomplete type, as myself during class definition, is forbidden, but since the template arguments differ, each *int_seq* inherits from a different class.

This **compile time (expanding) recursion**, causes the integer sequence to be embeeded in the variadic integer pack. We can mentally trace an example of the numbers during instantiation :

int_seq<3> inherits from int_seq<2, 3> int_seq<2, 3> inherits from int_seq<1, 2, 3> int_seq<1, 2, 3> inherits from int_seq<0, 1, 2, 3> int_seq<0, 1, 2, 3> contains { 0, 1, 2, 3 }

So **how do we use this thing** ? The “secret” is to **infer** the integer sequence. Let’s showcase this by returning to our first use case:

template<int... Is> void fU(ints<Is...>&& s) { for (auto i : { Is... }) cout << i << " "; cout << endl; } int main() { fU(IS<5>()); }

Since the sequence can’t “live” on its own, it’s used through a pack type container *ints*. Yet inside *func* we can refer to the sequence *Is* since it has been inferred; all it took was placing it in a deducable context!

## CodeKata

Now **make a reverse integer list**. I was tempted to submit a proposal for an STL extension (*make_reverse_integer_sequence*) but after solving this discovered (not to my surprise I admit) that it has been done before (just look at [2]).

So here’s my take at this:

// reverse integer sequence --------------------- template<int C, int N, int... Is> struct rev_seq : rev_seq<C - 1, N, N - C, Is...> { }; template<int N, int... Is> struct rev_seq<0, N, Is...> { using type = ints<N, Is...>; }; // convenience alias ---------------------------- template<int N> using RS = typename rev_seq<N, N>::type;

## Post scriptum

Related code can be found in the blog’s repository. A demo can be found here. Lastly, here’s a list of problems, in ascending order of difficulty :

- Trace the instantiation for
*RS<3>*in the CodeKata. - Tweak the code to provide the open sets (most implementations out there work this way, so that’s an easy one).
- Make a reverse integer list by reversing the front one.
- Make [N1, N2] ranges, ie ranges that can have their starting point specified eg
[2,6] -> { 2, 3, 4, 5, 6 }

- Make [N1, N2, step] ranges, ie ranges that can have their starting point and step specified eg
[2,6,2] -> { 2, 4, 6 }

Hopefully I’ll get some responses on the above and compile the highlights (along with some commenting) in an upcoming post.

Your implementation is a good proof of concept but its unlikely to be practical: the number of template instantiations grow linearly and in a lot of useful use cases it will reach the maximum level of template recursion allowed by the compiler. It is possible to implement the integer sequence in a way that only a logarithmic number of instantiation are necessary, allowing really huge sequences. See the implementation of std::integer_sequence (which is the same thing from the C++14 standard) in LLVM libc++, for example.

LikeLike

Thanks for your comment.Yes, I’m aware. It was out of the post’s scope to provide an std level implementation. We should not underestimate the difficulty of such a thing; in section “Efficiency considerations” of the related proposal (link 1 in the references) the matter is touched (the inventors of the whole thing resort to compiler intrinsics for a ct recursion free solution). I could provide an implementation like this http://stackoverflow.com/a/17426611 but it’s my understanding that it would make the concept presented here more obscure. Finally I believe that I haven’t prompt the reader to prefer these implementations over the standard ones; if that’s the case I should re-read your comment and better clarify the post’s wording.

LikeLike