Spec-Zone.ru › C++

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)
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 - диапазон элементов для проверки (также искомое множество)
first2, last2 - диапазон элементов для поиска (также игла)
r1 - диапазон элементов для проверки (также искомое множество)
r2 - диапазон элементов для поиска (также игла)
pred - бинарный предикат для применения к спроецированным элементам
proj1 - проекция для применения к элементам в первом диапазоне
proj2 - проекция для применения к элементам во втором диапазоне

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

1) Возвращает значение ranges::subrange, которое является первым вхождением последовательности [first2, last2) (также игла) в диапазоне [first1, last1) (также искомое множество) после применения проекций proj1 и proj2 к элементам обеих последовательностей соответственно с последующим применением бинарного предиката pred для сравнения спроецированных элементов.

Если такое вхождение не найдено, возвращается ranges::subrange{last1, last1}. Если диапазон для поиска (также игла) пуст, то есть 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};
 
    // 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}

См. также

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

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

Spec-Zone.ru

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