Difference between revisions of "cpp/algorithm/adjacent find"
(Complexity for the "found" case had an erroneous "+1".) |
(Refining the "complexity" statement.) |
||
| Line 29: | Line 29: | ||
===Complexity=== | ===Complexity=== | ||
| − | Exactly the smaller of {{tt|(result - first)}} and {{tt|(last - | + | Exactly the smaller of {{tt|(result - first)}} and {{tt|((last - 1) - first)}} applications of the predicate where {{tt|result}} is the return value. |
===Possible implementation=== | ===Possible implementation=== | ||
Revision as of 12:41, 22 October 2012
Template:ddcl list begin <tr class="t-dsc-header">
<td><algorithm>
<td></td> <td></td> </tr> <tr class="t-dcl ">
<td >ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
<td > (1) </td> <td class="t-dcl-nopad"> </td> </tr> <tr class="t-dcl ">
<td >ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
<td > (2) </td> <td class="t-dcl-nopad"> </td> </tr> Template:ddcl list end
Searches the range [first, last) for two consecutive identical elements. The first version uses operator== to compare the elements, the second version uses the given binary predicate p.
Contents |
Parameters
| first, last | - | the range of elements to examine |
| p | - | binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following: bool pred(const Type1 &a, const Type2 &b); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) |
| Type requirements | ||
-ForwardIt must meet the requirements of LegacyForwardIterator.
| ||
Return value
an iterator to the first of the identical elements. If no such elements are found, last is returned
Complexity
Exactly the smaller of (result - first) and ((last - 1) - first) applications of the predicate where result is the return value.
Possible implementation
| First version |
|---|
template<class ForwardIt> ForwardIt adjacent_find(ForwardIt first, ForwardIt last) { if (first == last) { return last; } ForwardIt next = first; ++next; for (next != last; ++next, ++first) { if (*first == *next) { return first; } } return last; } |
| Second version |
template<class ForwardIt, BinaryPredicate p> ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPredicate p) { if (first == last) { return last; } ForwardIt next = first; ++next; for (next != last; ++next, ++first) { if (p(*first, *next)) { return first; } } return last; } |
Example
The following code finds a pair of equivalent integers in an array of intergers.
#include <algorithm> #include <iostream> int main() { std::vector<int> v1{0, 1, 2, 3, 40, 40, 5}; std::vector<int>::iterator result; result = std::adjacent_find(v1.begin(), v1.end()); if (result == v1.end()) { std::cout << "no matching adjacent elements"; } else { std::cout << "match at: " << std::distance(v1.begin(), result); } }
Output:
match at: 4
