std::ranges:: find_end

From cppreference.net

Определено в заголовке `<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)

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 .

Функциональные сущности, описанные на этой странице, являются алгоритмическими функциональными объектами (неформально известными как niebloids ), то есть:

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

Содержание

Параметры

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

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

1) ranges:: subrange < I1 > { } значение, инициализированное выражением { 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 > .

Сложность

Не более $S\cdot(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 << "В \"";
    for (const auto c : haystack)
        std::cout << c;
    std::cout << "\" найдено \"";
    for (const auto c : needle)
        std::cout << c;
    std::cout << "\" на позиции [" << 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) { // использует бинарный предикат
            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); }); // проецирует второй диапазон
    print(secret, found4);
    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => не найдено
}

Вывод:

В "password password word..." найдено "password" на позиции [9..17)
             ^^^^^^^^
В "password password word..." найдено "word" на позиции [18..22)
                      ^^^^
В "password password word..." найдено "ord" на позиции [19..22)
                       ^^^
В "password password word..." найдено "sword" на позиции [12..17)
                ^^^^^

Смотрите также

ranges::find_last ranges::find_last_if ranges::find_last_if_not (C++23) (C++23) (C++23)	находит последний элемент, удовлетворяющий определённым критериям (функциональный объект алгоритма)
ranges::find ranges::find_if ranges::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	находит последнюю последовательность элементов в определённом диапазоне (шаблон функции)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: find_end

Содержание

Параметры

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

Сложность

Примечания

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

Пример

Смотрите также