Boost logo

Boost :

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
> <> 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,
    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_

    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;


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at