Bruno Dutra wrote:
Peter,
I can confirm peeking at the code that at least clang ships a naive linear
recursion implementation of make_index_sequence and I read somewhere that
GCC doesn't do any better, however it's well known
http://stackoverflow.com/a/17426611/801438 it may be implemented in
O(log(n))
plus taking full advantage of memoization.
Since Part 2 of your article is all about benchmarking, have you actually
tried it?
Yes, the timings in Part 2 use a log N integer_sequence.
// integer_sequence
template struct integer_sequence
{
};
template struct append_integer_sequence;
template struct
append_integer_sequence, integer_sequence>
{
using type = integer_sequence< T, I..., ( J + sizeof...(I) )... >;
};
template struct make_integer_sequence_impl;
template using make_integer_sequence = typename
make_integer_sequence_impl::type;
template struct make_integer_sequence_impl_
{
private:
static T const M = N / 2;
static T const R = N % 2;
using S1 = make_integer_sequence;
using S2 = typename append_integer_sequence::type;
using S3 = make_integer_sequence;
using S4 = typename append_integer_sequence::type;
public:
using type = S4;
};
template struct make_integer_sequence_impl: mp_if_c< N == 0,
mp_identity, mp_if_c< N == 1,
mp_identity>, make_integer_sequence_impl_ > >
{
};
// index_sequence
template using index_sequence =
integer_sequence;
template using make_index_sequence =
make_integer_sequence;
