[/ File find_backward.qbk]

[section:find_backward find_backward ]

[/license
Copyright (c) 2018 T. Zachary Laine

Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
]

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.

[heading 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.

[heading 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()

[heading Iterator Requirements]

All variants work on bidirectional iterators.

[heading Complexity]

Linear.

[heading 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.

[heading Notes]

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

[endsect]

[/ File equal.qbk
Copyright 2018 T. Zachary Laine
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt).
]