std::find_end

Определён в заголовке `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(1)	(constexpr начиная с C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(2)	(constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(начиная с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(4)	(начиная с C++17)

Ищет последнее вхождение целевого диапазона [first2, last2) в исходном диапазоне [first1, last1).

1) Элементы сравниваются с помощью operator==.

2) Элементы сравниваются с помощью заданного бинарного предиката p.

3,4) То же, что (1,2), но выполняется в соответствии с policy.

Эти перегрузки участвуют в разрешении перегрузки только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

first1, last1	-	пара итераторов, определяющая исходный диапазон
first2, last2	-	пара итераторов, определяющая целевой диапазон
p	-	бинарный предикат, который возвращает `true` если элементы должны считаться равными. Сигнатура функции предиката должна быть эквивалентна следующей: `bool pred(const Type1 &a, const Type2 &b);` Хотя сигнатура не обязана содержать `const &`, функция не должна модифицировать переданные ей объекты и должна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (таким образом, `Type1 &` не разрешён, а `Type1` не разрешён, если только для `Type1` перемещение не эквивалентно копированию(начиная с C++11)). Типы `Type1` и `Type2` должны быть такими, что объекты типов `ForwardIt1` и `ForwardIt2` можно разыменовать и затем неявно преобразовать в `Type1` и `Type2` соответственно.
policy	-	политика выполнения для использования
Требования к типам
- `ForwardIt1` должен соответствовать требованиям LegacyForwardIterator.
- `ForwardIt2` должен соответствовать требованиям LegacyForwardIterator.

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

Итератор на начало последнего вхождения целевого диапазона в исходном диапазоне.

Если целевой диапазон пуст или не встречается в исходном диапазоне, возвращается last1.

Сложность

Пусть $\scriptsize N_1$ $N 1$ равно std::distance(first1, last1) и $\scriptsize N_2$ $N 2$ равно std::distance(first2, last2):

1) Не более

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

сравнений с помощью operator==.

2) Не более

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

применений p.

3)

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

сравнений с помощью operator==.

4)

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

применений p.

Исключения

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

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

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

find_end (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2)
{
    if (first2 == last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, last2);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

find_end (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2, BinaryPred p)
{
    if (first2== last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, first2, p);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

Пример

Запустить этот код

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>

auto print_result = [](auto result, const auto& v)
{
    result == v.end()
        ? std::cout << "Sequence not found\n"
        : std::cout << "Last occurrence is at: " << std::distance(v.begin(), result)
                    << '\n';
};

int main()
{
    const auto v = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    
    for (const auto& x : {std::array{1, 2, 3}, {4, 5, 6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end()); // overload (1)
        print_result(iter, v);
    }
    
    for (const auto& x : {std::array{-1, -2, -3}, {-4, -5, -6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end(), // overload (3)
                                  [](int x, int y)
                                  {
                                      return std::abs(x) == std::abs(y);
                                  });
        print_result(iter, v);
    }
}

Вывод:

Last occurrence is at: 8
Sequence not found
Last occurrence is at: 8
Sequence not found

Отчёты о дефектах

Следующие отчёты о дефектах, изменяющие поведение, были применены к ранее опубликованным стандартам C++.

DR	Применён к	Поведение, указанное в публикации	Правильное поведение
LWG 1205	C++98	возвращаемое значение было неясным, если целевой диапазон пуст	возвращается `last1` в этом случае
LWG 2150	C++98	условие «вхождения» было неверным	исправлено

Смотри также

ranges::find_end (C++20)	находит последнюю последовательность элементов в определённом диапазоне (алгоритм-объект функции)
search	ищет первое вхождение диапазона элементов (шаблон функции & алгоритм-объект функции)
ranges::search (C++20)
includes	определяет, является ли одна последовательность подпоследовательностью другой (шаблон функции & алгоритм-объект функции)
ranges::includes (C++20)
adjacent_find	находит первые два соседних элемента, которые равны (или удовлетворяют заданному предикату) (шаблон функции & алгоритм-объект функции)
ranges::adjacent_find (C++20)
findfind_iffind_if_not (C++11)	находит первый элемент, удовлетворяющий определённым критериям (шаблон функции & алгоритм-объект функции)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
find_first_of	ищет любой элемент из набора элементов (шаблон функции & алгоритм-объект функции)
ranges::find_first_of (C++20)
search_n	ищет первое вхождение последовательности из нескольких последовательных копий элемента в диапазоне (шаблон функции & алгоритм-объект функции)
ranges::search_n (C++20)

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

ru.cppreference.net

Namespaces

Variants