Spec-Zone.ru › C++

std::find_first_of

Определено в заголовке <algorithm>
template< class InputIt, class ForwardIt >
InputIt find_first_of( InputIt first1, InputIt last1,
                       ForwardIt first2, ForwardIt last2 );
(1) (constexpr с C++20)
template< class InputIt, class ForwardIt, class BinaryPred >
InputIt find_first_of( InputIt first1, InputIt last1,
                       ForwardIt first2, ForwardIt last2,
                       BinaryPred p );
(2) (constexpr с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_first_of( ExecutionPolicy&& policy,
                          ForwardIt1 first1, ForwardIt1 last1,
                          ForwardIt2 first2, ForwardIt2 last2 );
(3) (с C++17)
template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class BinaryPred >
ForwardIt1 find_first_of( ExecutionPolicy&& policy,
                          ForwardIt1 first1, ForwardIt last1,
                          ForwardIt2 first2, ForwardIt2 last2,
                          BinaryPred p );
(4) (с C++17)

Выполняет поиск в исходном диапазоне [first1, last1) любого из элементов целевого диапазона [first2, last2).

1) Элементы сравниваются с помощью operator==.
2) Элементы сравниваются с помощью заданного бинарного предиката p.
3,4) То же, что и (1,2), но выполнение производится в соответствии с 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)

Параметры

first1, last1 - пара итераторов, задающих исходный диапазон
first2, last2 - пара итераторов, задающих целевой диапазон
p - бинарный предикат, возвращающий ​true, если элементы следует считать равными.

Сигнатура функции-предиката должна быть эквивалентна следующей:

boolpred(constType1&a,constType2&b);

Хотя сигнатура не обязана содержать const &, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) Type1 и Type2 независимо от категории значения (поэтому Type1 & не допускается, как и Type1, если только для Type1 перемещение не эквивалентно копированию(начиная с C++11)).
Типы Type1 и Type2 должны быть такими, чтобы объекты типов ForwardIt1 и ForwardIt2 можно было разыменовать, а полученные значения неявно преобразовать соответственно к Type1 и Type2. ​

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

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

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

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

Сложность

Пусть \(\scriptsize N_1\)N1 — std::distance(first1, last1), а \(\scriptsize N_2\)N2 — std::distance(first2, last2):

1) Не более \(\scriptsize N_1 \cdot N_2\)N1⋅N2 сравнений с помощью operator==.
2) Не более \(\scriptsize N_1 \cdot N_2\)N1⋅N2 вызовов p.
3) \(\scriptsize \mathcal{O}(N_1 \cdot N_2)\)𝓞(N1⋅N2) сравнений с помощью operator==.
4) \(\scriptsize \mathcal{O}(N_1 \cdot N_2)\)𝓞(N1⋅N2) вызовов p.

Исключения

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

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

find_first_of (1)
template<class InputIt, class ForwardIt>
InputIt find_first_of(InputIt first1, InputIt last1,
                      ForwardIt first2, ForwardIt last2)
{
    for (; first1 != last1; ++first1)
        for (ForwardIt it = first2; it != last2; ++it)
            if (*first1 == *it)
                return first1;
    return last1;
}
find_first_of (2)
template<class InputIt, class ForwardIt, class BinaryPred>
InputIt find_first_of(InputIt first1, InputIt last1,
                      ForwardIt first2, ForwardIt last2,
                      BinaryPred p)
{
    for (; first1 != last1; ++first1)
        for (ForwardIt it = first2; it != last2; ++it)
            if (p(*first1, *it))
                return first1;
    return last1;
}

Пример

Следующий код выполняет поиск любого из заданных целых чисел в векторе целых чисел:

#include <algorithm>
#include <iostream>
#include <vector>

auto print_sequence = [](const auto id, const auto& seq, int pos = -1)
{
    std::cout << id << "{ ";
    for (int i{}; const auto& e : seq)
    {
        const bool mark{i == pos};
        std::cout << (i++ ? ", " : "");
        std::cout << (mark ? "[ " : "") << e << (mark ? " ]" : "");
    }
    std::cout << " }\n";
};

int main()
{
    const std::vector<int> v{0, 2, 3, 25, 5};
    const auto t1 = {19, 10, 3, 4};
    const auto t2 = {1, 6, 7, 9};
    
    auto find_any_of = [](const auto& v, const auto& t)
    {
        const auto result = std::find_first_of(v.begin(), v.end(),
                                               t.begin(), t.end());
        if (result == v.end())
        {
            std::cout << "No elements of v are equal to any element of ";
            print_sequence("t = ", t);
            print_sequence("v = ", v);
        }
        else
        {
            const auto pos = std::distance(v.begin(), result);
            std::cout << "Found a match (" << *result << ") at position " << pos;
            print_sequence(", where t = ", t);
            print_sequence("v = ", v, pos);
        }
    };
    
    find_any_of(v, t1);
    find_any_of(v, t2);
}

Вывод:

Found a match (3) at position 2, where t = { 19, 10, 3, 4 }
v = { 0, 2, [ 3 ], 25, 5 }
No elements of v are equal to any element of t = { 1, 6, 7, 9 }
v = { 0, 2, 3, 25, 5 }

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

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

DR Применяется к Опубликованное поведение Корректное поведение
LWG 576 C++98 first1 и last1 должны были быть LegacyForwardIterator им достаточно быть LegacyInputIterator
LWG 1205 C++98 возвращаемое значение не было определено, если целевой диапазон пуст в этом случае возвращает last1

См. также

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

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

Spec-Zone.ru

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