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