std::ranges::find_end

Определён в заголовочном файле `<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< /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 = identity, class Proj2 = identity> requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2> ranges::subrange<I1> find_end( 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 = identity, class Proj2 = identity> requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2> ranges::borrowed_subrange_t<R1> find_end( 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_2\cdot(N_1-N_2+1)\)N₂⋅(N₁-N₂+1) применений pred, proj1 и proj2.

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

Исключения

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

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

Примечания

Реализация может повысить эффективность поиска, если типы итераторов моделируют bidirectional_iterator, выполняя поиск от конца к началу. Моделирование 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::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 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;
    using std::ranges::find_end;
    
    constexpr auto secret{"password password word..."sv};
    constexpr auto wanted{"password"sv};
    
    constexpr auto found1 = find_end(secret.cbegin(), secret.cend(),
                                     wanted.cbegin(), wanted.cend());
    print(secret, found1);
    
    constexpr auto found2 = find_end(secret, "word"sv);
    print(secret, found2);
    
    const auto found3 = 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 = find_end(secret, "SWORD"sv, {}, {},
        [](char c) { return std::tolower(c); }); // projects the 2nd range
    print(secret, found4);
    
    static_assert(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)
                ^^^^^

См. также

find_end	находит последнюю последовательность элементов в заданном диапазоне (шаблон функции)
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)	выполняет поиск первого вхождения в диапазоне заданного числа последовательных копий элемента (объект-функция алгоритма)

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