Compile-time integer sequences

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 :

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.

References

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