• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1[/ File find_backward.qbk]
2
3[section:find_backward find_backward ]
4
5[/license
6Copyright (c) 2018 T. Zachary Laine
7
8Distributed under the Boost Software License, Version 1.0.
9(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
10]
11
12The header file 'find_backward.hpp' contains variants of the stl algorithm
13`find`. These variants are like `find`, except that the evaluate the elements
14of the given sequence in reverse order.
15
16Consider how finding the last element that is equal to `x` in a range is
17typically done:
18
19    // Assume a valid range if elements delimited by [first, last).
20    while (last-- != first) {
21        if (*last == x) {
22            // Use last here...
23        }
24    }
25
26Raw loops are icky though.  Perhaps we should do a bit of extra work to allow
27the use of `std::find()`:
28
29    auto rfirst = std::make_reverse_iterator(last);
30    auto rlast = std::make_reverse_iterator(first);
31    auto it = std::find(rfirst, rlast, x);
32    // Use it here...
33
34That seems nicer in that there is no raw loop, but it has two major drawbacks.
35First, it requires an unpleasant amount of typing.  Second, it is less
36efficient than forward-iterator `find` , since `std::reverse_iterator` calls
37its base-iterator's `operator--()` in most of its member functions before
38doing the work that the member function requires.
39
40[heading interface]
41
42    template<typename BidiIter, typename T>
43    BidiIter find_backward(BidiIter first, BidiIter last, const T & x);
44
45    template<typename Range, typename T>
46    boost::range_iterator<Range> find_backward(Range & range, const T & x);
47
48These overloads of `find_backward` return an iterator to the last element that
49is equal to `x` in `[first, last)` or `r`, respectively.
50
51    template<typename BidiIter, typename T>
52    BidiIter find_not_backward(BidiIter first, BidiIter last, const T & x);
53
54    template<typename Range, typename T>
55    boost::range_iterator<Range> find_not_backward(Range & range, const T & x);
56
57These overloads of `find_not_backward` return an iterator to the last element
58that is not equal to `x` in `[first, last)` or `r`, respectively.
59
60    template<typename BidiIter, typename Pred>
61    BidiIter find_if_backward(BidiIter first, BidiIter last, Pred p);
62
63    template<typename Range, typename Pred>
64    boost::range_iterator<Range> find_if_backward(Range & range, Pred p);
65
66These overloads of `find_if_backward` return an iterator to the last element
67for which `pred` returns `true` in `[first, last)` or `r`, respectively.
68
69    template<typename BidiIter, typename Pred>
70    BidiIter find_if_not_backward(BidiIter first, BidiIter last, Pred p);
71
72    template<typename Range, typename Pred>
73    boost::range_iterator<Range> find_if_not_backward(Range & range, Pred p);
74
75These overloads of `find_if_not_backward` return an iterator to the last
76element for which `pred` returns `false` in `[first, last)` or `r`,
77respectively.
78
79[heading Examples]
80
81Given the container `c1` containing `{ 2, 1, 2 }`, then
82
83    find_backward        ( c1.begin(), c1.end(), 2                          ) --> --c1.end()
84    find_backward        ( c1.begin(), c1.end(), 3                          ) --> c1.end()
85    find_if_backward     ( c1.begin(), c1.end(), [](int i) {return i == 2;} ) --> --c1.end()
86    find_if_backward     ( c1.begin(), c1.end(), [](int i) {return i == 3;} ) --> c1.end()
87    find_not_backward    ( c1.begin(), c1.end(), 2                          ) --> std::prev(c1.end(), 2)
88    find_not_backward    ( c1.begin(), c1.end(), 1                          ) --> c1.end()
89    find_if_not_backward ( c1.begin(), c1.end(), [](int i) {return i == 2;} ) --> std::prev(c1.end(), 2)
90    find_if_not_backward ( c1.begin(), c1.end(), [](int i) {return i == 1;} ) --> c1.end()
91
92[heading Iterator Requirements]
93
94All variants work on bidirectional iterators.
95
96[heading Complexity]
97
98Linear.
99
100[heading Exception Safety]
101
102All of the variants take their parameters by value and do not depend upon any
103global state. Therefore, all the routines in this file provide the strong
104exception guarantee.
105
106[heading Notes]
107
108All variants are `constexpr` in C++14 or later.
109
110[endsect]
111
112[/ File equal.qbk
113Copyright 2018 T. Zachary Laine
114Distributed under the Boost Software License, Version 1.0.
115(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt).
116]
117