Home | Libraries | People | FAQ | More |
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.
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.
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()
All variants work on bidirectional iterators.
Linear.
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.
All variants are constexpr
in
C++14 or later.