...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: |
x< if reverse_x< 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: |
x< if reverse_x< 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> > ));