Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Front Page / Algorithms / Transformation Algorithms / reverse_unique

reverse_unique

Synopsis

template<
      typename Seq
    , typename Pred
    , typename In = unspecified
    >
struct reverse_unique
{
    typedef unspecified type;
};

Description

Returns a sequence of the initial elements of every subrange of the reversed original sequence Seq whose elements are all the same.

[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/unique.hpp>

Model of

Reversible Algorithm

Parameters

Parameter Requirement Description
Sequence Forward Sequence An original sequence.
Pred Binary Lambda Expression An equivalence relation.
In Inserter An inserter.

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, a binary Lambda Expression pred, and an Inserter in:

typedef reverse_unique<s,pred,in>::type r;
Return type:

A type.

Semantics:

If size<s>::value <= 1, then equivalent to

typedef reverse_copy<s,in>::type r;

otherwise equivalent to

typedef lambda<pred>::type p;
typedef lambda<in::operation>::type in_op;
typedef apply_wrap2<
      in_op
    , in::state
    , front<types>::type
    >::type in_state;

typedef reverse_fold<
      s
    , pair< in_state, front<s>::type >
    , eval_if<
          apply_wrap2<p, second<_1>, _2>
        , identity< first<_1> >
        , apply_wrap2<in_op, first<_1>, _2>
        >
    >::type::first r;

Complexity

Linear. Performs exactly size<s>::value - 1 applications of pred, and at most size<s>::value insertions.

Example

typedef vector<int,float,float,char,int,int,int,double> types;
typedef vector<double,int,char,float,int> expected;
typedef reverse_unique< types, is_same<_1,_2> >::type result;

BOOST_MPL_ASSERT(( equal< result,expected > ));

See also

Transformation Algorithms, Reversible Algorithm, unique, reverse_remove, reverse_copy_if, replace_if