Boost C++ Libraries

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.