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 1$ как ranges::distance(first1, last1) или ranges::distance(r1), и $\scriptsize N_2$ $N 2$ как ranges::distance(first2, last2) или ranges::distance(r2):

1,2) не более

N 2 \cdot(N 1 -N 2 +1)

применений pred и proj.

3,4)

𝓞(N 2 \cdot(N 1 -N 2 +1))

применений pred и proj.

Исключения

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

Поддержка компилятора
Автономные и хостируемые окружения
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Именованные требования
Макросы тестирования возможностей (C++20)
Библиотека поддержки языка
Библиотека концепций (C++20)
Библиотека диагностики
Библиотека управления памятью
Библиотека метапрограммирования (C++11)
Библиотека общих утилит
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека строк
Библиотека обработки текста
Библиотека численных операций
Библиотека даты и времени
Библиотека ввода/вывода
Библиотека файловой системы (C++17)
Библиотека поддержки параллелизма (C++11)
Библиотека управления выполнением (C++26)
Технические спецификации
Индекс символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants