std::ranges::search

Определён в заголовочном файле `<algorithm>`
Сигнатура вызова
template< std::forward_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 ranges::subrange<I1> search( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(начиная с C++20)
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_subrange_t<R1> search( 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> ranges::subrange<I1> search( 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> constexpr ranges::borrowed_subrange_t<R1> search( 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	-	политика выполнения

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

Поддиапазон, соответствующий первому вхождению целевого диапазона в исходном диапазоне.

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

Сложность

Обозначим

\(\scriptsize N_1\)N₁ как ranges::distance(first1, last1) или ranges::distance(r1), а
\(\scriptsize N_2\)N₂ как ranges::distance(first2, last2) или ranges::distance(r2):

1,2) Не более \(\scriptsize N_1 \cdot N_2\)N₁⋅N₂ применений pred, proj1 и proj2.

3,4) \(\scriptsize \mathcal{O}(N_1 \cdot N_2)\)𝓞(N₁⋅N₂) применений pred, proj1 и proj2.

Исключения

3,4) Во время выполнения:

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

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

struct search_fn
{
    template<std::forward_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 ranges::subrange<I1>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (;; ++first1)
        {
            I1 it1 = first1;
            for (I2 it2 = first2;; ++it1, ++it2)
            {
                if (it2 == last2)
                    return {first1, it1};
                if (it1 == last1)
                    return {it1, it1};
                if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2)))
                    break;
            }
        }
    }
    
    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_subrange_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 search_fn search{};

Пример

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string_view>

using namespace std::literals;

void print(int id, const auto& haystack, const auto& needle, const auto& found)
{
    std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); ";
    const auto first = std::distance(haystack.begin(), found.begin());
    const auto last = std::distance(haystack.begin(), found.end());
    if (found.empty())
        std::cout << "not found;";
    else
    {
        std::cout << "found: \"";
        for (const auto x : found)
            std::cout << x;
        std::cout << "\";";
    }
    std::cout << " subrange: {" << first << ", " << last << "}\n";
}

int main()
{
    constexpr auto haystack{"abcd abcd"sv};
    constexpr auto needle{"bcd"sv};
    
    // the search uses iterator pairs begin()/end():
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    
    // the search uses ranges r1, r2:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    
    // “needle” range is empty:
    constexpr auto none{""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    
    // “needle” will not be found:
    constexpr auto awl{"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    
    // the search uses custom comparator and projections:
    constexpr auto bodkin{"234"sv};
    auto found5 = std::ranges::search(haystack, bodkin,
        [](const int x, const int y) { return x == y; }, // pred
        [](const int x) { return std::toupper(x); }, // proj1
        [](const int y) { return y + 'A' - '1'; }); // proj2
    print(5, haystack, bodkin, found5);
}

Вывод:

1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}

См. также

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

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