Since C++14 a generator for compile-time integer sequences is available in the standard library. How does this work? How to create your own implementation if this is not available in your distribution? How to modify the sequence? Here, we want to look at these questions and want to show and analyze some different implementations found in the web.
A compile-time integer sequence is a variadic class template with integer non-type template parameters, e.g.
Sometimes it is necessary to have a specific sequence of increasing values, that
can be used in parameter pack expansions. As an example we want to store all values
std::array in a C-Array, using the template function
Here, an integer sequence is used as a function parameter that can be deduces
and unpacked automatically, to have all the indices at hand and to be used in
a pack expansion:
The question is, how to generate the template
for any given upper index
The simplest (direct) approach has linear complexity in the template recursion
depth and recursively pushes back an integer number to the sequence. If we have
the template class
Seq as above, then a push-back class that adds an integer to
the end of a sequence could look like:
for the specialization, since
Seq itself provides a
An integer sequence can now be generated, by adding the upper index recursively
to an already generated smaller sequence. Therefore, we have to write a break
condition for the smallest sequence, e.g. a sequence with length 0. We
write a template class
MakeSeq<N> with a
type attribute, that represents the
Seq<0,1,...,N-1> sequence with N integers:
or a bit shorter:
That’s it. A small test could be to compare the length of the sequence to N:
another variant of the sequential implementation to create an integer sequence
is published. There, the break condition is realized using a
statement and the
PushBack helper class is included in the
MakeSeq class directly.
This may reduce the number of templates to be instantiated by the compiler and may be
preferable in this context:
Motivated by the implementation in the standard library a variant of the integer
sequence generation is provided that works directly on the variadic integer
sequences, i.e. the
Seq template, and adds a type attribute
represents a sequence with one more integer appended:
The generator template
MakeSeq now simply adds an alias that calls the
A measurement of the time to instantiate (generate) the integer-sequence shows, that
there is a difference between compilers and also between the way of implementing
the classes, i.e. using an own type attribute (Version A), deriving from the
Seq class (Version B), or using the Stackoverflow one-class implementation (Version C).
For LENGTH=900 we get the average timings in seconds
for the call
COMPILER -std=c++11 -DLENGTH=900 -ftemplate-depth=1000 SOURCE.cc. The
clang compilers have problems with larger
LENGTH parameters and stop with a
Segmentation fault. This is not the case for g++. There the template instantiation
depth could be increased a lot further.
How to improve the implementation further? In a linear implementation where indices are appended to the sequence one by one, the compiler can not reuse already instantiated parts of the template and must go down the full depth.
A recursive implementation with logarithmic instantiation depth can be formulated by splitting the sequence into two parts [0,N/2] and [N/2+1,N], creating sequences for both parts recursively, and finally concatenating the partial sequences.
The first implementation creates a linear sequence [start, start+1, start+2, …, end] by splitting in the middle of the interval [start, end]. Therefore, we introduce a template with two parameters and a corresponding alias template as shortcut:
MakeSeq class can be recapitulated from
MakeSeqImpl by template specialization:
here implemented as alias template.
Similar to the
PushBack template of above, a
Concat template is used that
pushes all the indices from the second sequence at the end of the indices of the
The implementation of
MakeSeqImpl now calls
Concat of two subsequences:
A slightly more involved implementation introduces a shift in the concatenation and creates recursively two sequences that do overlap, where the second one is shifted by the length of the first one. This variant is show on Stackoverflow/Answer-1 by user Xeo.
Concat template is modified slightly:
MakeSeq class can now be implemented directly, without the help of the
where the parameter
N is now, as before, the length of the sequence. We need both
break conditions, since each of those can not be implemented without the other one.
The advantage of this variant is that both ranges may be the same and thus, the compiler may reuse the instantiation of one.
the user Khurshid posted an answer that uses this idea even more strictly,
by creating twice the same sequence and concatenating those, using
above. Only in the case that
N is not divisible by two, a final index is added
to the sequence.
IncSeq_if implements the push-back of the final index, in the case that the
first template argument is
Concat is slightly modified to reuse the same sequence twice:
In a same way as above we measure the time to compile the various variants of the logarithmic integer sequence implementation, using the compilers clang and g++:
We see that the compilation times are about a factor > 5 lower than for the linear implementation and that the most specialized variant F outperforms all the other implementations. Thus, it makes sense to optimize the way of instantiating templates when large instantiation depth are necessary and if we want to reduce compilation times.
Download source files
You can download all the source-files, by following the links in the table below: