...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 / Concepts / Reversible Algorithm |
A Reversible Algorithm is a member of a pair of transformation algorithms that iterate over their input sequence(s) in opposite directions. For each reversible algorithm x there exists a counterpart algorithm reverse_x, that exhibits the exact semantics of x except that the elements of its input sequence argument(s) are processed in the reverse order.
In the following table and subsequent specifications, x is a placeholder token for the actual Reversible Algorithm's name, s_{1},s_{2},...s_{n} are Forward Sequences, and in is an Inserter.
Expression | Type | Complexity |
---|---|---|
x<s_{1},s_{2},...s_{n}, ...>::type | Forward Sequence | Unspecified. |
x<s_{1},s_{2},...s_{n}, ... in>::type | Any type | Unspecified. |
reverse_x<s_{1},s_{2},...s_{n}, ...>::type | Forward Sequence | Unspecified. |
reverse_x<s_{1},s_{2},...s_{n}, ... in>::type | Any type | Unspecified. |
typedef x<s_{1},s_{2},...s_{n},...>::type t;
Precondition: | s_{1} is an Extensible Sequence. |
---|---|
Semantics: | t is equivalent to x< s_{1},s_{2},...s_{n},... , back_inserter< clear<s_{1}>::type > >::type if has_push_back<s_{1}>::value == true and reverse_x< s_{1},s_{2},...s_{n},... , front_inserter< clear<s_{1}>::type > >::type otherwise. |
typedef x<s_{1},s_{2},...s_{n},...in>::type t;
Semantics: | t is the result of an x invocation with arguments s_{1},s_{2},... s_{n},...in. |
---|
typedef reverse_x<s_{1},s_{2},... s_{n},... >::type t;
Precondition: | s_{1} is an Extensible Sequence. |
---|---|
Semantics: | t is equivalent to x< s_{1},s_{2},...s_{n},... , front_inserter< clear<s_{1}>::type > >::type if has_push_front<s_{1}>::value == true and reverse_x< s_{1},s_{2},...s_{n},... , back_inserter< clear<s_{1}>::type > >::type otherwise. |
typedef reverse_x<s_{1},s_{2},...s_{n},... in>::type t;
Semantics: | t is the result of a reverse_x invocation with arguments s_{1},s_{2},...s_{n},...in. |
---|
typedef transform< range_c<int,0,10> , plus<_1,int_<7> > , back_inserter< vector0<> > >::type r1; typedef transform< r1, minus<_1,int_<2> > >::type r2; typedef reverse_transform< r2 , minus<_1,5> , front_inserter< vector0<> > >::type r3; BOOST_MPL_ASSERT(( equal<r1, range_c<int,7,17> > )); BOOST_MPL_ASSERT(( equal<r2, range_c<int,5,15> > )); BOOST_MPL_ASSERT(( equal<r3, range_c<int,0,10> > ));