Compile-time integer sequences


 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:
    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()

 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!


 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 :

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


  1. Proposal N3658 
  2. reversing a list by Xeo
  3. the earliest implementaion I could find, by Johannes Schaub

2 thoughts on “Compile-time integer sequences

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


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s