| Home | Libraries | People | FAQ | More

### find_backward

The header file 'find_backward.hpp' contains variants of the stl algorithm `find`. These variants are like `find`, except that the evaluate the elements of the given sequence in reverse order.

Consider how finding the last element that is equal to `x` in a range is typically done:

    // Assume a valid range if elements delimited by [first, last).
    while (last-- != first) {
        if (*last == x) {
            // Use last here...
        }
    }

Raw loops are icky though. Perhaps we should do a bit of extra work to allow the use of `std::find()`:

    auto rfirst = std::make_reverse_iterator(last);
    auto rlast = std::make_reverse_iterator(first);
    auto it = std::find(rfirst, rlast, x);
    // Use it here...

That seems nicer in that there is no raw loop, but it has two major drawbacks. First, it requires an unpleasant amount of typing. Second, it is less efficient than forward-iterator `find` , since `std::reverse_iterator` calls its base-iterator's `operator--()` in most of its member functions before doing the work that the member function requires.

##### interface

    template<typename BidiIter, typename T>
    BidiIter find_backward(BidiIter first, BidiIter last, const T & x);

    template<typename Range, typename T>
    boost::range_iterator<Range> find_backward(Range & range, const T & x);

These overloads of `find_backward` return an iterator to the last element that is equal to `x` in `[first, last)` or `r`, respectively.

    template<typename BidiIter, typename T>
    BidiIter find_not_backward(BidiIter first, BidiIter last, const T & x);

    template<typename Range, typename T>
    boost::range_iterator<Range> find_not_backward(Range & range, const T & x);

These overloads of `find_not_backward` return an iterator to the last element that is not equal to `x` in `[first, last)` or `r`, respectively.

    template<typename BidiIter, typename Pred>
    BidiIter find_if_backward(BidiIter first, BidiIter last, Pred p);

    template<typename Range, typename Pred>
    boost::range_iterator<Range> find_if_backward(Range & range, Pred p);

These overloads of `find_if_backward` return an iterator to the last element for which `pred` returns `true` in `[first, last)` or `r`, respectively.

    template<typename BidiIter, typename Pred>
    BidiIter find_if_not_backward(BidiIter first, BidiIter last, Pred p);

    template<typename Range, typename Pred>
    boost::range_iterator<Range> find_if_not_backward(Range & range, Pred p);

These overloads of `find_if_not_backward` return an iterator to the last element for which `pred` returns `false` in `[first, last)` or `r`, respectively.

##### Examples

Given the container `c1` containing `{ 2, 1, 2 }`, then

    find_backward        ( c1.begin(), c1.end(), 2                          ) --> --c1.end()
    find_backward        ( c1.begin(), c1.end(), 3                          ) --> c1.end()
    find_if_backward     ( c1.begin(), c1.end(), [](int i) {return i == 2;} ) --> --c1.end()
    find_if_backward     ( c1.begin(), c1.end(), [](int i) {return i == 3;} ) --> c1.end()
    find_not_backward    ( c1.begin(), c1.end(), 2                          ) --> std::prev(c1.end(), 2)
    find_not_backward    ( c1.begin(), c1.end(), 1                          ) --> c1.end()
    find_if_not_backward ( c1.begin(), c1.end(), [](int i) {return i == 2;} ) --> std::prev(c1.end(), 2)
    find_if_not_backward ( c1.begin(), c1.end(), [](int i) {return i == 1;} ) --> c1.end()

##### Iterator Requirements

All variants work on bidirectional iterators.

##### Complexity

Linear.

##### Exception Safety

All of the variants take their parameters by value and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.

##### Notes

All variants are `constexpr` in C++14 or later.