Spec-Zone.ru › C++

std::find, std::find_if, std::find_if_not

Определён в заголовке <algorithm>
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
(1) (constexpr с C++20)
(до C++26)
template< class InputIt, class T = typename std::iterator_traits
                                       <InputIt>::value_type >
constexpr InputIt find( InputIt first, InputIt last, const T& value );
(с C++26)
template< class InputIt, class UnaryPred >
InputIt find_if( InputIt first, InputIt last, UnaryPred p );
(2) (constexpr с C++20)
template< class InputIt, class UnaryPred >
InputIt find_if_not( InputIt first, InputIt last, UnaryPred q );
(3) (с C++11)
(constexpr с C++20)
template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt find( ExecutionPolicy&& policy,
                ForwardIt first, ForwardIt last, const T& value );
(4) (с C++17)
(до C++26)
template< class ExecutionPolicy,
          class ForwardIt, class T = typename std::iterator_traits
                                         <ForwardIt>::value_type >
ForwardIt find( ExecutionPolicy&& policy,
                ForwardIt first, ForwardIt last, const T& value );
(с C++26)
template< class ExecutionPolicy, class ForwardIt, class UnaryPred >
ForwardIt find_if( ExecutionPolicy&& policy,
                   ForwardIt first, ForwardIt last, UnaryPred p );
(5) (с C++17)
template< class ExecutionPolicy, class ForwardIt, class UnaryPred >
ForwardIt find_if_not( ExecutionPolicy&& policy,
                       ForwardIt first, ForwardIt last, UnaryPred q );
(6) (с C++17)

Возвращает итератор на первый элемент исходного диапазона [first, last), удовлетворяющий заданному условию (или last, если такого итератора нет).

1) find выполняет поиск первого элемента, равного value (с использованием operator==).
2) find_if выполняет поиск первого элемента, для которого предикат p возвращает true.
3) find_if_not выполняет поиск первого элемента, для которого предикат q возвращает false.
4-6) Аналогично (1-3), но выполняется согласно policy.
Эти перегрузки участвуют в разрешении перегрузки только в том случае, если значение следующего выражения равно true:

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

(до C++20)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

(с C++20)

Параметры

first, last - пара итераторов, задающих исходный диапазон
value - значение, с которым сравниваются элементы
p - унарный предикат, который возвращает ​true для требуемого элемента.

Выражение p(v) должно быть преобразуемо в bool для каждого аргумента v типа (возможно, const) VT, где VT — тип значения InputIt, независимо от категории значения; выражение не должно изменять v. Поэтому тип параметра VT&не допускается, как и VT, если только для VT перемещение не эквивалентно копированию(с C++11). ​

q - унарный предикат, который возвращает ​false для требуемого элемента.

Выражение q(v) должно быть преобразуемо в bool для каждого аргумента v типа (возможно, const) VT, где VT — тип значения InputIt, независимо от категории значения; выражение не должно изменять v. Поэтому тип параметра VT&не допускается, как и VT, если только для VT перемещение не эквивалентно копированию(с C++11). ​

policy - политика выполнения, которую следует использовать
Требования к типам
-InputIt должен соответствовать требованиям LegacyInputIterator.
-ForwardIt должен соответствовать требованиям LegacyForwardIterator.
-UnaryPredicate должен соответствовать требованиям Predicate.

Возвращаемое значение

Первый итератор it в исходном диапазоне, удовлетворяющий следующему условию, или last, если такого итератора нет:

1,4) *it == value равно true.
2,5) p(*it) равно true.
3,6) q(*it) равно false.

Сложность

Пусть \(\scriptsize N\)N — это std::distance(first, last):

1) Не более \(\scriptsize N\)N сравнений с value с использованием operator==.
2) Не более \(\scriptsize N\)N применений p.
3) Не более \(\scriptsize N\)N применений q.
4) \(\scriptsize \mathcal{O}(N)\)𝓞(N) сравнений с value с использованием operator==.
5) \(\scriptsize \mathcal{O}(N)\)𝓞(N) применений p.
6) \(\scriptsize \mathcal{O}(N)\)𝓞(N) применений q.

Исключения

4-6) В ходе выполнения:
  • Если временные ресурсы памяти, необходимые для распараллеливания, недоступны, выбрасывается std::bad_alloc.
  • Если при доступе к объектам через аргумент алгоритма возникает необработанное исключение, поведение определяется политикой выполнения (для стандартных политик вызывается std::terminate).

Возможная реализация

find
template<class InputIt, class T = typename std::iterator_traits<InputIt>::value_type>
constexpr InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first)
        if (*first == value)
            return first;
    
    return last;
}
find_if
template<class InputIt, class UnaryPred>
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPred p)
{
    for (; first != last; ++first)
        if (p(*first))
            return first;
    
    return last;
}
find_if_not
template<class InputIt, class UnaryPred>
constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPred q)
{
    for (; first != last; ++first)
        if (!q(*first))
            return first;
    
    return last;
}

Примечания

Если C++11 недоступен, эквивалентом std::find_if_not будет использование std::find_if с отрицанием предиката.

template<class InputIt, class UnaryPred>
InputIt find_if_not(InputIt first, InputIt last, UnaryPred q)
{
    return std::find_if(first, last, std::not1(q));
}
Макрос проверки поддержки функции Значение Стандарт Функция
__cpp_lib_algorithm_default_value_type 202403 (C++26) Инициализация списком для алгоритмов (1,4)

Пример

В следующем примере выполняется поиск чисел в заданных последовательностях.

#include <algorithm>
#include <array>
#include <cassert>
#include <complex>
#include <initializer_list>
#include <iostream>
#include <vector>

bool is_even(int i)
{
    return i % 2 == 0;
}

void example_contains()
{
    const auto haystack = {1, 2, 3, 4};
    
    for (const int needle : {3, 5})
        if (std::find(haystack.begin(), haystack.end(), needle) == haystack.end())
            std::cout << "haystack does not contain " << needle << '\n';
        else
            std::cout << "haystack contains " << needle << '\n';
}

void example_predicate()
{
    for (const auto& haystack : {std::array{3, 1, 4}, {1, 3, 5}})
    {
        const auto it = std::find_if(haystack.begin(), haystack.end(), is_even);
        if (it != haystack.end())
            std::cout << "haystack contains an even number " << *it << '\n';
        else
            std::cout << "haystack does not contain even numbers\n";
    }
}

void example_list_init()
{
    std::vector<std::complex<double>> haystack{{4.0, 2.0}};
#ifdef __cpp_lib_algorithm_default_value_type
    // T gets deduced making list-initialization possible
    const auto it = std::find(haystack.begin(), haystack.end(), {4.0, 2.0});
#else
    const auto it = std::find(haystack.begin(), haystack.end(), std::complex{4.0, 2.0});
#endif
    assert(it == haystack.begin());  
}

int main()
{
    example_contains();
    example_predicate();
    example_list_init();
}

Вывод:

haystack contains 3
haystack does not contain 5
haystack contains an even number 4
haystack does not contain even numbers

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были ретроактивно применены к ранее опубликованным стандартам C++.

Отчёт об ошибке Применён к Опубликованное поведение Корректное поведение
LWG 283 C++98 T требовалось быть EqualityComparable, однако
тип значения InputIt мог не быть T
требование удалено

См. также

ranges::findranges::find_ifranges::find_if_not
(C++20)(C++20)(C++20)
находит первый элемент, удовлетворяющий заданному условию
(объект-функция алгоритма)
adjacent_find
находит первые два соседних элемента, которые равны (или удовлетворяют заданному предикату)
(шаблон функции и объект-функция алгоритма)
ranges::adjacent_find
(C++20)
find_end
находит последнюю последовательность элементов в заданном диапазоне
(шаблон функции и объект-функция алгоритма)
ranges::find_end
(C++20)
find_first_of
выполняет поиск любого элемента из заданного набора
(шаблон функции и объект-функция алгоритма)
ranges::find_first_of
(C++20)
mismatch
находит первую позицию, в которой два диапазона различаются
(шаблон функции и объект-функция алгоритма)
ranges::mismatch
(C++20)
search
выполняет поиск первого вхождения диапазона элементов
(шаблон функции и объект-функция алгоритма)
ranges::search
(C++20)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/find

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API