std::ranges::find_end

Определено в заголовке <algorithm>

Подпись вызова

Определено в заголовке `<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> find_end( 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> find_end( R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(с C++20)

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>
    find_end( 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>
    find_end( R1&& r1, R2&& r2, Pred pred = {},
              Proj1 proj1 = {}, Proj2 proj2 = {} );

(2)

(с C++20)

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

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

Функциональные сущности, описанные на этой странице, являются неблоидами, то есть:

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

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

Параметры

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

Значение результата

1) Значение, инициализированное выражением {i, i + (i == last1 ? 0 : ranges::distance(first2, last2))}, которое обозначает последнее вхождение последовательности [first2, last2) в диапазоне [first1, last1) (после проекций с помощью proj1 и proj2). Если [first2, last2) пуст или такая последовательность не найдена, значение результата инициализируется значением {last1, last1}.

2) То же, что и (1), за исключением того, что тип результата — ranges::borrowed_subrange_t<R1>.

Сложность

Максимум \(\scriptsize S\cdot(N-S+1)\)S·(N-S+1) применений соответствующего предиката и каждой проекции, где \(\scriptsize S\)S является ranges::distance(first2, last2) и \(\scriptsize N\)N — ranges::distance(first1, last1) для (1), или \(\scriptsize S\)S — ranges::distance(r2) и \(\scriptsize N\)N — ranges::distance(r1) для (2).

Примечания

Реализация может повысить эффективность поиска, если входные итераторы моделируют std::bidirectional_iterator , выполняя поиск с конца к началу. Моделирование std::random_access_iterator может улучшить скорость сравнения. Однако все это не меняет теоретической сложности худшего случая.

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

struct find_end_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
    {
        if (first2 == last2)
        {
            auto last_it = ranges::next(first1, last1);
            return {last_it, last_it};
        }
        auto result = ranges::search(
            std::move(first1), last1, first2, last2, pred, proj1, proj2);
 
        if (result.empty())
            return result;
 
        for (;;)
        {
            auto new_result = ranges::search(
                std::next(result.begin()), last1, first2, last2, pred, proj1, proj2);
            if (new_result.empty())
                return result;
            else
                result = std::move(new_result);
        }
    }
 
    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 find_end_fn find_end {};

Пример

#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>
 
void print(const auto haystack, const auto needle)
{
    const auto pos = std::distance(haystack.begin(), needle.begin());
    std::cout << "In \"";
    for (const auto c : haystack)
        std::cout << c;
    std::cout << "\" found \"";
    for (const auto c : needle)
        std::cout << c;
    std::cout << "\" at position [" << pos << ".." << pos + needle.size() << ")\n"
        << std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}
 
int main()
{
    using namespace std::literals;
    constexpr auto secret{"password password word..."sv};
    constexpr auto wanted{"password"sv};
 
    constexpr auto found1 = std::ranges::find_end(
        secret.cbegin(), secret.cend(), wanted.cbegin(), wanted.cend());
    print(secret, found1);
 
    constexpr auto found2 = std::ranges::find_end(secret, "word"sv);
    print(secret, found2);
 
    const auto found3 = std::ranges::find_end(secret, "ORD"sv,
        [](const char x, const char y) { // uses a binary predicate
            return std::tolower(x) == std::tolower(y);
        });
    print(secret, found3);
 
    const auto found4 = std::ranges::find_end(secret, "SWORD"sv, {}, {},
        [](char c) { return std::tolower(c); }); // projects the 2nd range
    print(secret, found4);
 
    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => not found
}

Вывод:

In "password password word..." found "password" at position [9..17)
             ^^^^^^^^
In "password password word..." found "word" at position [18..22)
                      ^^^^
In "password password word..." found "ord" at position [19..22)
                       ^^^
In "password password word..." found "sword" at position [12..17)
                ^^^^^

См. также

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

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