std::ranges:: search

From cppreference.net

Определено в заголовке `<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)

1) Ищет первое вхождение последовательности элементов

first2

last2

в диапазоне

first1

last1

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

2) То же, что и (1) , но использует r1 в качестве первого исходного диапазона и r2 в качестве второго исходного диапазона, как если бы использовались ranges:: begin ( r1 ) как first1 , ranges:: end ( r1 ) как last1 , ranges:: begin ( r2 ) как first2 , и ranges:: end ( r2 ) как last2 .

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

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

Содержание

Параметры

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

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

1) Возвращает значение ranges:: subrange , которое является первым вхождением последовательности

first2

last2

(также называемой needle ) в диапазоне

first1

last1

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

Если такое вхождение не найдено, возвращается ranges:: subrange { last1, last1 } .

Если диапазон для поиска (также называемый needle ) пуст, то есть first2 == last2 , тогда возвращается ranges:: subrange { first1, first1 } .

2) То же, что и (1) , но возвращаемый тип — ranges:: borrowed_subrange_t < R1 > .

Сложность

Максимум S * N применений соответствующего предиката и каждой проекции, где
(1) S = ranges:: distance ( first2, last2 ) и N = ranges:: distance ( first1, last1 ) ;
(2) S = ranges:: distance ( r2 ) и N = ranges:: distance ( r1 ) .

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

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::end(r1),
                       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};
    // поиск использует пары итераторов begin()/end():
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    // поиск использует диапазоны r1, r2:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    // диапазон 'needle' пуст:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle' не будет найден:
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    // поиск использует пользовательский компаратор и проекции:
    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}

Смотрите также

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

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants