Spec-Zone.ru › C++

std::ranges::find_first_of

Определён в заголовочном файле <algorithm>
Сигнатура вызова 
template< std::input_iterator I1, std::sentinel_for<I1> S1,
          std::forward_iterator I2, std::sentinel_for<I2> S2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr I1
    find_first_of( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {} );
(1) (начиная с C++20) 
template< ranges::input_range R1, ranges::forward_range R2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
constexpr ranges::borrowed_iterator_t<R1>
    find_first_of( R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {} );
(2) (начиная с C++20) 
template< /*execution-policy*/ Ep,
          std::random_access_iterator I1, std::sized_sentinel_for<I1> S1,
          std::random_access_iterator I2, std::sized_sentinel_for<I2> S2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
I1 find_first_of( Ep&& policy, I1 first1, S1 last1, I2 first2, S2 last2,
                  Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
(3) (начиная с C++26) 
template< /*execution-policy*/ Ep,
          /*sized-random-access-range*/ R1,
          /*sized-random-access-range*/ R2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
ranges::borrowed_iterator_t<R1>
    find_first_of( Ep&& policy, R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {} );
(4) (начиная с C++26)

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

Ищет в исходном диапазоне любой из элементов целевого диапазона. Элементы (к которым применены проекции proj1 и proj2 соответственно) сравниваются с помощью бинарного предиката pred.

1) Исходный диапазон — [first1, last1), а целевой диапазон — [first2, last2).
2) Исходный диапазон — r1, а целевой диапазон — r2.
3,4) То же, что и (1,2), но выполняется в соответствии с policy.

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

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

Параметры

first1, last1 - пара итератора и сентинела, задающая исходный диапазон
first2, last2 - пара итератора и сентинела, задающая целевой диапазон
r1 - исходный диапазон
r2 - целевой диапазон
pred - предикат, применяемый к элементам (после проекции)
proj1 - проекция, применяемая к элементам исходного диапазона
proj2 - проекция, применяемая к элементам целевого диапазона
policy - политика выполнения

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

Итератор на первый элемент исходного диапазона, совпадающий с элементом целевого диапазона.

Если целевой диапазон пуст или такой элемент не найден, возвращается:

1,3) ranges::next(first1, last1)
2,4) ranges::next(ranges::begin(r1), ranges::end(r1))

Сложность

Пусть \(\scriptsize N_1\)N1 — ranges::distance(first1, last1) или ranges::distance(r1), а \(\scriptsize N_2\)N2 — ranges::distance(first2, last2) или ranges::distance(r2):

1,2) Не более \(\scriptsize N_1 \cdot N_2\)N1⋅N2 применений pred и proj.
3,4) \(\scriptsize \mathcal{O}(N_1 \cdot N_2)\)𝓞(N1⋅N2) применений pred и proj.

Исключения

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

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

struct find_first_of_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::forward_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr I1 operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                            Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; first1 != last1; ++first1)
            for (auto i = first2; i != last2; ++i)
                if (std::invoke(pred, std::invoke(proj1, *first1), std::invoke(proj2, *i)))
                    return first1;
        return first1;
    }
    
    template<ranges::input_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
    constexpr ranges::borrowed_iterator_t<R1>
        operator()(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2),
                       ranges::next(ranges::begin(r2), ranges::end(r2)),
                       std::move(pred), std::move(proj1), std::move(proj2));
    }
    
    template<ranges::forward_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
    constexpr ranges::borrowed_iterator_t<R1>
        operator()(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1),
                       ranges::next(ranges::begin(r1), ranges::end(r1)),
                       ranges::begin(r2),
                       ranges::next(ranges::begin(r2), ranges::end(r2)),
                       std::move(pred), std::move(proj1), std::move(proj2));
    }
};

inline constexpr find_first_of_fn find_first_of{};

Пример

#include <algorithm>
#include <iostream>
#include <iterator>

int main()
{
    using std::ranges::find_first_of;
    
    constexpr static auto haystack = {1, 2, 3, 4};
    constexpr static auto needles  = {0, 3, 4, 3};
    
    constexpr auto found1 = find_first_of(haystack.begin(), haystack.end(),
                                          needles.begin(), needles.end());
    static_assert(std::distance(haystack.begin(), found1) == 2);
    
    constexpr auto found2 = find_first_of(haystack, needles);
    static_assert(std::distance(haystack.begin(), found2) == 2);
    
    constexpr static auto negatives = {-6, -3, -4, -3};
    constexpr auto not_found = find_first_of(haystack, negatives);
    static_assert(not_found == haystack.end());
    
    constexpr auto found3 = find_first_of(haystack, negatives,
        [](int x, int y) { return x == -y; }); // uses a binary comparator
    static_assert(std::distance(haystack.begin(), found3) == 2);
    
    struct P { int x, y; };
    constexpr static auto p1 = {P{1, -1}, P{2, -2}, P{3, -3}, P{4, -4}};
    constexpr static auto p2 = {P{5, -5}, P{6, -3}, P{7, -5}, P{8, -3}};
    
    // Compare only P::y data members by projecting them:
    const auto found4 = find_first_of(p1, p2, {}, &P::y, &P::y);
    std::cout << "First equivalent element {" << found4->x << ", " << found4->y
              << "} was found at position " << std::distance(p1.begin(), found4)
              << ".\n";
}

Вывод:

First equivalent element {3, -3} was found at position 2.

См. также

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

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

Spec-Zone.ru

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