Spec-Zone.ru › C++

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

Определён в заголовочном файле <algorithm>
Сигнатура вызова 
template< std::input_iterator I, std::sentinel_for<I> S,
          class T, class Proj = std::identity >
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr I find( I first, S last, const T& value, Proj proj = {} );
(1) (начиная с C++20)
(до C++26) 
template< std::input_iterator I, std::sentinel_for<I> S,
          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr I find( I first, S last, const T& value, Proj proj = {} );
(начиная с C++26) 
template< ranges::input_range R, class T, class Proj = std::identity >
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr ranges::borrowed_iterator_t<R>
    find( R&& r, const T& value, Proj proj = {} );
(2) (начиная с C++20)
(до C++26) 
template< ranges::input_range R, class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr ranges::borrowed_iterator_t<R>
    find( R&& r, const T& value, Proj proj = {} );
(начиная с C++26) 
template< std::input_iterator I, std::sentinel_for<I> S,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
constexpr I find_if( I first, S last, Pred pred, Proj proj = {} );
(3) (начиная с C++20) 
template< ranges::input_range R, class Proj = std::identity,
          std::indirect_unary_predicate
              <std::projected<ranges::iterator_t<R>, Proj>> Pred >
constexpr ranges::borrowed_iterator_t<R>
    find_if( R&& r, Pred pred, Proj proj = {} );
(4) (начиная с C++20) 
template< std::input_iterator I, std::sentinel_for<I> S,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
constexpr I find_if_not( I first, S last, Pred pred, Proj proj = {} );
(5) (начиная с C++20) 
template< ranges::input_range R, class Proj = std::identity,
          std::indirect_unary_predicate
              <std::projected<ranges::iterator_t<R>, Proj>> Pred >
constexpr ranges::borrowed_iterator_t<R>
    find_if_not( R&& r, Pred pred, Proj proj = {} );
(6) (начиная с C++20) 
template< /*execution-policy*/ Ep,
          std::random_access_iterator I, std::sized_sentinel_for<I> S,
          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
I find( Ep&& policy, I first, S last, const T& value, Proj proj = {} );
(7) (начиная с C++26) 
template< /*execution-policy*/ Ep, /*sized-random-access-range*/ R,
          class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
ranges::borrowed_iterator_t<R>
    find( Ep&& policy, R&& r, const T& value, Proj proj = {} );
(8) (начиная с C++26) 
template< /*execution-policy*/ Ep,
          std::random_access_iterator I, std::sized_sentinel_for<I> S,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
I find_if( Ep&& policy, I first, S last, Pred pred, Proj proj = {} );
(9) (начиная с C++26) 
template< /*execution-policy*/ Ep, /*sized-random-access-range*/ R,
          class Proj = std::identity,
          std::indirect_unary_predicate
              <std::projected<ranges::iterator_t<R>, Proj>> Pred >
ranges::borrowed_iterator_t<R>
    find_if( Ep&& policy, R&& r, Pred pred, Proj proj = {} );
(10) (начиная с C++26) 
template< /*execution-policy*/ Ep,
          std::random_access_iterator I, std::sized_sentinel_for<I> S,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
I find_if_not( Ep&& policy, I first, S last, Pred pred, Proj proj = {} );
(11) (начиная с C++26) 
template< /*execution-policy*/ Ep, /*sized-random-access-range*/ R,
          class Proj = std::identity,
          std::indirect_unary_predicate
              <std::projected<ranges::iterator_t<R>, Proj>> Pred >
ranges::borrowed_iterator_t<R>
    find_if_not( Ep&& policy, R&& r, Pred pred, Proj proj = {} );
(12) (начиная с C++26)

Определение /*execution-policy*/ см. на этой странице; определение /*sized-random-access-range*/ см. на этой странице.

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

1,2) find выполняет поиск первого элемента, равного целевому значению value.
3,4) find_if выполняет поиск первого элемента, для которого предикат pred возвращает true.
5,6) find_if_not выполняет поиск первого элемента, для которого предикат pred возвращает false.
7-12) То же, что и (1-6), но выполнение осуществляется в соответствии с policy.

Функциональные объекты, описанные на этой странице, являются функциональными объектами алгоритмов (неофициально называемыми niebloids), то есть:

  • При вызове любого из них нельзя указывать явные списки аргументов шаблона.
  • Ни один из них не виден для поиска с учетом аргументов.
  • Если какой-либо из них найден с помощью обычного неквалифицированного поиска как имя слева от оператора вызова функции, поиск с учетом аргументов не выполняется.

Параметры

first, last - пара итератора и сентинела, задающая исходный диапазон
r - исходный диапазон
value - целевое значение
pred - предикат, применяемый к (преобразованным) элементам
proj - проекция, применяемая к элементам
policy - политика выполнения, которая будет использоваться

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

Итератор на первый элемент, удовлетворяющий условию.

Если такой элемент не найден, возвращает ranges::next(first, last) (или ranges::next(ranges::begin(r), ranges::end(r)) для перегрузок с диапазонами).

Сложность

Пусть \(\scriptsize N\)N — ranges::distance(first, last) или ranges::distance(r):

1,2) Не более \(\scriptsize N\)N сравнений и применений proj.
3-6) Не более \(\scriptsize N\)N применений pred и proj.
7,8) \(\scriptsize \mathcal{O}(N)\)𝓞(N) сравнений и применений proj.
9-12) \(\scriptsize \mathcal{O}(N)\)𝓞(N) применений pred и proj.

Исключения

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

Примечания

Макрос проверки поддержки функции Значение Стандарт Функция
__cpp_lib_algorithm_default_value_type 202403 (C++26) Инициализация списком для алгоритмов (1,2)

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

find 
struct find_fn
{
    template<std::input_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>>
        requires std::indirect_binary_predicate
                     <ranges::equal_to, std::projected<I, Proj>, const T*>
    constexpr I operator()(I first, S last, const T& value, Proj proj = {}) const
    {
        for (; first != last; ++first)
            if (std::invoke(proj, *first) == value)
                return first;
        return first;
    }
    
    template<ranges::input_range R, class T, class Proj = std::identity>
        requires std::indirect_binary_predicate
                     <ranges::equal_to,
                      std::projected<ranges::iterator_t<R>, Proj>, const T*>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, const T& value, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value, std::ref(proj));
    }
    
    template<ranges::forward_range R, class T, class Proj = std::identity>
        requires std::indirect_binary_predicate
                     <ranges::equal_to,
                      std::projected<ranges::iterator_t<R>, Proj>, const T*>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, const T& value, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r),
                       ranges::next(ranges::begin(r), ranges::end(r)),
                       value, std::ref(proj));
    }
};

inline constexpr find_fn find;
find_if 
struct find_if_fn
{
    template<std::input_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
    constexpr I operator()(I first, S last, Pred pred, Proj proj = {}) const
    {
        for (; first != last; ++first)
            if (std::invoke(pred, std::invoke(proj, *first)))
                return first;
        return first;
    }
    
    template<ranges::input_range R, class Proj = std::identity,
             std::indirect_unary_predicate
                 <std::projected<ranges::iterator_t<R>, Proj>> Pred>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Pred pred, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::ref(pred), std::ref(proj));
    }
    
    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_unary_predicate
                 <std::projected<ranges::iterator_t<R>, Proj>> Pred>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Pred pred, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r),
                       ranges::next(ranges::begin(r), ranges::end(r)),
                       std::ref(pred), std::ref(proj));
    }
};

inline constexpr find_if_fn find_if;
find_if_not 
struct find_if_not_fn
{
    template<std::input_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
    constexpr I operator()(I first, S last, Pred pred, Proj proj = {}) const
    {
        for (; first != last; ++first)
            if (!std::invoke(pred, std::invoke(proj, *first)))
                return first;
        return first;
    }
    
    template<ranges::input_range R, class Proj = std::identity,
             std::indirect_unary_predicate
                 <std::projected<ranges::iterator_t<R>, Proj>> Pred>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Pred pred, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::ref(pred), std::ref(proj));
    }
    
    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_unary_predicate
                 <std::projected<ranges::iterator_t<R>, Proj>> Pred>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Pred pred, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r),
                       ranges::next(ranges::begin(r), ranges::end(r)),
                       std::ref(pred), std::ref(proj));
    }
};

inline constexpr find_if_not_fn find_if_not;

Пример

#include <algorithm>
#include <cassert>
#include <complex>
#include <format>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

void projector_example()
{
    struct folk_info
    {
        unsigned uid;
        std::string name, position;
    };
    
    std::vector<folk_info> folks
    {
        {0, "Ana", "dev"},
        {1, "Bob", "devops"},
        {2, "Eve", "ops"}
    };
    
    const auto who{"Eve"};
    if (auto it = std::ranges::find(folks, who, &folk_info::name); it != folks.end())
        std::cout << std::format("Profile:\n"
                                 "    UID: {}\n"
                                 "    Name: {}\n"
                                 "    Position: {}\n\n",
                                 it->uid, it->name, it->position);
}

int main()
{
    namespace ranges = std::ranges;
    
    projector_example();
    
    const int n1 = 3;
    const int n2 = 5;
    const auto v = {4, 1, 3, 2};
    
    if (ranges::find(v, n1) != v.end())
        std::cout << "v contains: " << n1 << '\n';
    else
        std::cout << "v does not contain: " << n1 << '\n';
    
    if (ranges::find(v.begin(), v.end(), n2) != v.end())
        std::cout << "v contains: " << n2 << '\n';
    else
        std::cout << "v does not contain: " << n2 << '\n';
    
    auto is_even = [](int x) { return x % 2 == 0; };
    
    if (auto result = ranges::find_if(v.begin(), v.end(), is_even); result != v.end())
        std::cout << "First even element in v: " << *result << '\n';
    else
        std::cout << "No even elements in v\n";
    
    if (auto result = ranges::find_if_not(v, is_even); result != v.end())
        std::cout << "First odd element in v: " << *result << '\n';
    else
        std::cout << "No odd elements in v\n";
    
    auto divides_13 = [](int x) { return x % 13 == 0; };
    
    if (auto result = ranges::find_if(v, divides_13); result != v.end())
        std::cout << "First element divisible by 13 in v: " << *result << '\n';
    else
        std::cout << "No elements in v are divisible by 13\n";
    
    if (auto result = ranges::find_if_not(v.begin(), v.end(), divides_13);
        result != v.end())
        std::cout << "First element indivisible by 13 in v: " << *result << '\n';
    else
        std::cout << "All elements in v are divisible by 13\n";
    
    std::vector<std::complex<double>> nums{{4, 2}};
    #ifdef __cpp_lib_algorithm_default_value_type
        // T gets deduced in (2) making list-initialization possible
        const auto it = ranges::find(nums, {4, 2});
    #else
        const auto it = ranges::find(nums, std::complex<double>{4, 2});
    #endif
    assert(it == nums.begin());
}

Вывод:

Profile:
    UID: 2
    Name: Eve
    Position: ops

v contains: 3
v does not contain: 5
First even element in v: 4
First odd element in v: 1
No elements in v are divisible by 13
First element indivisible by 13 in v: 4

См. также

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

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

Spec-Zone.ru

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