Difference between revisions of "cpp/algorithm/find"
m (break line) |
m (→Complexity: Apparently, distance(first,last) is more correct, even though I.S. shortens it to the (last - first) notation. Shouldn't all std #Complexity sections of algos be patched in this manner?) |
||
Line 70: | Line 70: | ||
===Complexity=== | ===Complexity=== | ||
− | At most {{tt| | + | At most {{tt|N}} applications of the predicate, where {{c|1= N = std::distance(first, last)}}. |
+ | |||
===Exceptions=== | ===Exceptions=== | ||
{{cpp/algorithm/parallel_exceptions_reporting_behavior}} | {{cpp/algorithm/parallel_exceptions_reporting_behavior}} |
Revision as of 09:59, 11 August 2021
Defined in header <algorithm>
|
||
(1) | ||
template< class InputIt, class T > InputIt find( InputIt first, InputIt last, const T& value ); |
(until C++20) | |
template< class InputIt, class T > constexpr InputIt find( InputIt first, InputIt last, const T& value ); |
(since C++20) | |
template< class ExecutionPolicy, class ForwardIt, class T > ForwardIt find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, |
(2) | (since C++17) |
(3) | ||
template< class InputIt, class UnaryPredicate > InputIt find_if( InputIt first, InputIt last, |
(until C++20) | |
template< class InputIt, class UnaryPredicate > constexpr InputIt find_if( InputIt first, InputIt last, |
(since C++20) | |
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate > ForwardIt find_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, |
(4) | (since C++17) |
(5) | ||
template< class InputIt, class UnaryPredicate > InputIt find_if_not( InputIt first, InputIt last, |
(since C++11) (until C++20) |
|
template< class InputIt, class UnaryPredicate > constexpr InputIt find_if_not( InputIt first, InputIt last, |
(since C++20) | |
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate > ForwardIt find_if_not( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, |
(6) | (since C++17) |
Returns an iterator to the first element in the range [first, last)
that satisfies specific criteria:
find
searches for an element equal to value
find_if
searches for an element for which predicate p
returns truefind_if_not
searches for an element for which predicate q
returns falsepolicy
. These overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true. |
(until C++20) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true. |
(since C++20) |
Contents |
Parameters
first, last | - | the range of elements to examine |
value | - | value to compare the elements to |
policy | - | the execution policy to use. See execution policy for details. |
p | - | unary predicate which returns true for the required element. The expression p(v) must be convertible to bool for every argument |
q | - | unary predicate which returns false for the required element. The expression q(v) must be convertible to bool for every argument |
Type requirements | ||
-InputIt must meet the requirements of LegacyInputIterator.
| ||
-ForwardIt must meet the requirements of LegacyForwardIterator.
| ||
-UnaryPredicate must meet the requirements of Predicate.
|
Return value
Iterator to the first element satisfying the condition or last
if no such element is found.
Complexity
At most N
applications of the predicate, where N = std::distance(first, last).
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies, std::terminate is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory, std::bad_alloc is thrown.
Possible implementation
First version |
---|
template<class InputIt, class T> constexpr InputIt find(InputIt first, InputIt last, const T& value) { for (; first != last; ++first) { if (*first == value) { return first; } } return last; } |
Second version |
template<class InputIt, class UnaryPredicate> constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p) { for (; first != last; ++first) { if (p(*first)) { return first; } } return last; } |
Third version |
template<class InputIt, class UnaryPredicate> constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q) { for (; first != last; ++first) { if (!q(*first)) { return first; } } return last; } |
Notes
If you do not have C++11, an equivalent to std::find_if_not
is to use std::find_if
with the negated predicate.
template<class InputIt, class UnaryPredicate> InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q) { return std::find_if(first, last, std::not1(q)); } |
Example
The following example finds integers in given vector.
#include <iostream> #include <algorithm> #include <vector> #include <iterator> int main() { std::vector<int> v{1, 2, 3, 4}; int n1 = 3; int n2 = 5; auto is_even = [](int i){ return i%2 == 0; }; auto result1 = std::find(begin(v), end(v), n1); auto result2 = std::find(begin(v), end(v), n2); auto result3 = std::find_if(begin(v), end(v), is_even); (result1 != std::end(v)) ? std::cout << "v contains " << n1 << '\n' : std::cout << "v does not contain " << n1 << '\n'; (result2 != std::end(v)) ? std::cout << "v contains " << n2 << '\n' : std::cout << "v does not contain " << n2 << '\n'; (result3 != std::end(v)) ? std::cout << "v contains an even number: " << *result3 << '\n' : std::cout << "v does not contain even numbers\n"; }
Output:
v contains 3 v does not contain 5 v contains an even number: 2
See also
finds the first two adjacent items that are equal (or satisfy a given predicate) (function template) | |
finds the last sequence of elements in a certain range (function template) | |
searches for any one of a set of elements (function template) | |
finds the first position where two ranges differ (function template) | |
searches for the first occurrence of a range of elements (function template) | |
(C++20)(C++20)(C++20) |
finds the first element satisfying specific criteria (niebloid) |