Namespaces
Variants

std::ranges::search

Из ru.cppreference.net
 
 
Библиотека алгоритмов
Ограниченные алгоритмы и алгоритмы над диапазонами (C++20)
Ограниченные алгоритмы, например ranges::copy, ranges::sort, ...
Операции над последовательностями без изменения    
Пакетные операции
(C++17)
Операции поиска
Операции изменения последовательностей
Операции копирования
(C++11)
(C++11)
Операции обмена
Операции преобразования
Операции заполнения
Операции удаления
Операции изменения порядка
(до C++17)(C++11)
(C++20)(C++20)
Операции выборки
(C++17)

Сортировка и связанные операции
Операции разделения
(C++11)    

Операции сортировки
Операции бинарного поиска
(по разбитым диапазонам)
Операции над множествами (по отсортированным диапазонам)
Операции слияния (по отсортированным диапазонам)
Операции с кучей
Операции минимума/максимума
(C++11)
(C++17)
Операции лексикографического сравнения
Операции перестановок


Политики выполнения (C++17)
(только для пояснения*)(C++26)

Численные операции
(C++11)
(C++17)
(C++17)    

Специализированные <memory> алгоритмы

Специализированные <random> алгоритмы
Библиотека C









 
Ограниченные алгоритмы
Все имена в этом меню принадлежат пространству имён std::ranges
Операции над последовательностями без изменения
Операции изменения последовательностей
Операции разделения
Операции сортировки
Операции бинарного поиска (по отсортированным диапазонам)
       
       
Операции над множествами (по отсортированным диапазонам)
Операции с кучей
Операции минимума/максимума
       
       
Операции перестановок
Операции свёртки
Операции над неинициализированной памятью
Типы возврата
 
Определено в заголовке <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}

См. также

находит первые два смежных элемента, которые равны (или удовлетворяют заданному предикату)
(объект-функция алгоритма)
находит первый элемент, удовлетворяющий определённым критериям
(объект-функция алгоритма)
находит последнюю последовательность элементов в заданном диапазоне
(объект-функция алгоритма)
ищет любой из набора элементов
(объект-функция алгоритма)
проверяет, содержит ли диапазон заданный элемент или поддиапазон
(объект-функция алгоритма)
определяет, является ли одна последовательность подпоследовательностью другой
(объект-функция алгоритма)
находит первую позицию, где два диапазона различаются
(объект-функция алгоритма)
ищет первое вхождение нескольких последовательных копий элемента в диапазоне
(объект-функция алгоритма)
ищет первое вхождение диапазона элементов
(шаблон функции)