Re: [boost] [utility] [C++0x] indices/make_indices

From: David Abrahams (dave_at_[hidden])
Date: 2008-07-19 21:04:55

on Sat Jul 19 2008, Joel de Guzman <joel-AT-boost-consulting.com> wrote:

> David Abrahams wrote:
>
>> Wow, looking at the tuples code it seems there's a lot of optimization
>> we can do now!
>
> So...
>
> deref(advance(begin(tuple)), n)
>
> where advance is implemented as
>
> iterator advance(iterator x, int n)
> {
>    if (n == 0)
>        return x;
>    else
>        return ++advance(x, n - 1); // corrected
> }
>
> Isn't this what we are already doing in fusion?

Nope...

>     template <>
>     struct at_impl<cons_tag>
>     {
>         template <typename Sequence, typename N>
>         struct apply
>         {
>             typedef typename
>                 mpl::eval_if<
>                     is_const<Sequence>
>                   , add_const<typename Sequence::cdr_type>
>                   , mpl::identity<typename Sequence::cdr_type>
>                 >::type
>             cdr_type;
>
>             typedef typename
>                 mpl::eval_if<
>                     mpl::bool_<N::value == 0>
>                   , mpl::identity<typename Sequence::car_type>
>                   , apply<cdr_type, mpl::int_<N::value-1> >
                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This instantiates the template on the cdr with N-1 iterations
i.e., it's like advance(++x, n-1)
You need ++advance(x, n-1) to avoid O(N^2)

>                 >
>             element;

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com