Re: [boost] "Simple C++11 metaprogramming"

Subject: Re: [boost] "Simple C++11 metaprogramming"
From: Peter Dimov (lists_at_[hidden])
Date: 2015-07-24 05:10:25

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<class T, T... I> struct integer_sequence
{
};

template<class S1, class S2> struct append_integer_sequence;

template<class T, T... I, T... J> struct 
append_integer_sequence<integer_sequence<T, I...>, integer_sequence<T, 
J...>>
{
    using type = integer_sequence< T, I..., ( J + sizeof...(I) )... >;
};

template<class T, T N> struct make_integer_sequence_impl;

template<class T, T N> using make_integer_sequence = typename 
make_integer_sequence_impl<T, N>::type;

template<class T, T N> struct make_integer_sequence_impl_
{
private:

    static T const M = N / 2;
    static T const R = N % 2;

    using S1 = make_integer_sequence<T, M>;
    using S2 = typename append_integer_sequence<S1, S1>::type;
    using S3 = make_integer_sequence<T, R>;
    using S4 = typename append_integer_sequence<S2, S3>::type;

public:

    using type = S4;
};

template<class T, T N> struct make_integer_sequence_impl: mp_if_c< N == 0, 
mp_identity<integer_sequence<T>>, mp_if_c< N == 1, 
mp_identity<integer_sequence<T, 0>>, make_integer_sequence_impl_<T, N> > >
{
};

// index_sequence

template<std::size_t... I> using index_sequence = 
integer_sequence<std::size_t, I...>;

template<std::size_t N> using make_index_sequence = 
make_integer_sequence<std::size_t, N>;