reverse_stable_partition

Synopsis

template<
      typename Seq
    , typename Pred
    , typename In1 = unspecified
    , typename In2 = unspecified
    >
struct reverse_stable_partition
{
    typedef unspecified type;
};

Returns a pair of sequences together containing all elements in the range [begin<Seq>::type, end<Seq>::type) split into two groups based on the predicate Pred. reverse_stable_partition is guaranteed to preserve the reversed relative order of the elements in the resulting sequences.

[Note: This wording applies to a no-inserter version(s) of the algorithm. See the Expression semantics subsection for a precise specification of the algorithm's details in all cases — end note]

Header

#include <boost/mpl/stable_partition.hpp>

Model of

Reversible Algorithm

Parameters

Parameter	Requirement	Description
`Seq`	Forward Sequence	An original sequence.
`Pred`	Unary Lambda Expression	A partitioning predicate.
`In1`, `In2`	Inserter	Output inserters.

Expression semantics

The semantics of an expression are defined only where they differ from, or are not defined in Reversible Algorithm.

For any Forward Sequence s, an unary Lambda Expression pred, and Inserters in1 and in2:

typedef reverse_stable_partition<s,pred,in1,in2>::type r;

Return type: A pair.

Semantics:

Return type:	A `pair`.
Semantics:	Equivalent to typedef lambda<pred>::type p; typedef lambda<in1::operation>::type in1_op; typedef lambda<in2::operation>::type in2_op; typedef reverse_fold< s , pair< in1::state, in2::state > , if_< apply_wrap`1`<p,_2> , pair< apply_wrap`2`<in1_op,first<_1>,_2>, second<_1> > , pair< first<_1>, apply_wrap`2`<in2_op,second<_1>,_2> > > >::type r;

Equivalent to

typedef lambda<pred>::type p;
typedef lambda<in1::operation>::type in1_op;
typedef lambda<in2::operation>::type in2_op;

typedef reverse_fold<
      s
    , pair< in1::state, in2::state >
    , if_< 
          apply_wrap1<p,_2>
        , pair< apply_wrap2<in1_op,first<_1>,_2>, second<_1> >
        , pair< first<_1>, apply_wrap2<in2_op,second<_1>,_2> >
        >
    >::type r;

Complexity

Linear. Exactly size<s>::value applications of pred, and size<s>::value of summarized in1::operation / in2::operation applications.

Example

template< typename N > struct is_odd : bool_<(N::value % 2)> {};

typedef reverse_stable_partition<
      range_c<int,0,10> 
    , is_odd<_1>
    , back_inserter< vector<> >
    , back_inserter< vector<> >
    >::type r;

BOOST_MPL_ASSERT(( equal< r::first, vector_c<int,9,7,5,3,1> > ));
BOOST_MPL_ASSERT(( equal< r::second, vector_c<int,8,6,4,2,0> > ));