Subject: Re: [boost] [mpl]iter_fold_if Forward Backward rationale?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2009-04-02 17:16:49
On 04/02/09 14:34, Larry Evans wrote:
> On 03/13/09 18:49, David Abrahams wrote:
[snip]
> Lists can only be constructed backwards because lists don't have a
> push_back? IOW, with only a push_front, the lists have to be
> constructed:
>
> push_front
> < push_front
> < push_front
> < list<>
> , i3
> >
> , i2
> >
> , i1
> >
>
> to create list<i1,i2,i3>? So, a traversal from back to front,
> (i3->i1), is needed, and, for example,
>
> fold<vector<i1,i2,i3>,list<>, push_front<_,_> >
>
> would give:
>
> list<i3,i2,i1>
>
> Instead, to create list<i1,i2,i3> from some sequence, S<i1,i2,i3>,
> reverse_fold would be needed:
>
> reverse_fold<S<i1,i2,i3>,list<>, push_front<_,_> >
>
> Is that about what you mean?
>
[snip]
One reason I'm interested is that I can't figure out how reverse_fold
would work on a sequence, S, such that begin<S>::type with just a
forward iterator. I would have thought that you'd need a
bidirectional iterator in order to traverse backwards; yet:
https://svn.boost.org/trac/boost/browser/trunk/libs/mpl/test/fold.cpp#L46
shows that it works on lists. Another reason I'm interested is that
both vector and list are implemented using what looks like binary
operators, v_item, and l_item, and I'm wondering why they couldn't be
done with some sort of fold method. After all the vector
super:
v_item<T_i, vector<T_i-1,T_i-2,...> >
looks like it could be done with a fold. Inspired by that example,
I actually coded one:
-{--code fold_reverse--
template
< typename IterNow
, typename IterEnd
, typename State
, typename ForwardOp
, typename NextOp=next<arg<1> >
>
struct
fold_reverse_iter
: apply
< ForwardOp
, typename fold_reverse_iter
< typename apply<NextOp,IterNow>::type
, IterEnd
, State
, ForwardOp
, NextOp
>::type
, IterNow
>
{
};
template
< typename IterEnd
, typename State
, typename ForwardOp
, typename NextOp
>
struct
fold_reverse_iter
< IterEnd
, IterEnd
, State
, ForwardOp
, NextOp
>
{
typedef
State
type
;
};
template
< class Sequence
, class State
, class ForwardOp
>
struct
fold_reverse
: fold_reverse_iter
< typename begin<Sequence>::type
, typename end<Sequence>::type
, State
, typename lambda<ForwardOp>::type::template
apply
< arg<1>
, deref<arg<2> >
>
>
{
};
-}--code fold_reverse--
Note how similar it is to the normal fold for the variadic compiler:
-{--code fold--
template
< typename IterNow
, typename IterEnd
, typename State
, typename ForwardOp
, typename NextOp=next<arg<1> >
>
struct
fold_iter
: fold_iter
< typename apply<NextOp,IterNow>::type
, IterEnd
, typename apply<ForwardOp,State,IterNow>::type
, ForwardOp
, NextOp
>
{
};
template
< typename IterEnd
, typename State
, typename ForwardOp
, typename NextOp
>
struct
fold_iter
< IterEnd
, IterEnd
, State
, ForwardOp
, NextOp
>
{
typedef
State
type
;
};
template
< typename Sequence
, typename State
, typename ForwardOp
>
struct
fold
: fold_iter
< typename begin<Sequence>::type
, typename end<Sequence>::type
, State
, typename lambda<ForwardOp>::type::template
apply
< arg<1>
, deref<arg<2> >
>
>
{
};
-}--code fold--
So, back to v_item and fold_reverse_iter.
The difference is that instead of:
v_item
< T0
, vector<T...>
>
in fold_reverse_iter there's:
apply
< ForwardOp
, typename fold_reverse_iter
< typename apply<NextOp,IterNow>::type
, IterEnd
, State
, ForwardOp
, NextOp
>::type
, IterNow
>
where ForwardOp would be push_front<arg<1>, deref<arg<2> > >.
So, my next question is what's the advantage of using v_item<
vector<T...> > instead of using fold_reverse_iter? I guess you could
say it's more complicated, but then it reuses code and it's not (IMO)
that much more complicated. OTOH, using iter_fold_if is more
complicated and the justification may be that it also reuses code;
however, I'm wondering if it could be simplified by using something
like the fold_reverse_iter.
-regards,
Larry