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