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
Advertisements

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.

    Like

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

      Like

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s