std::find_end

Определено в заголовке `<algorithm>`
	(1)
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );		(до C++20)
template< class ForwardIt1, class ForwardIt2 > constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );	(2)	(с C++17)
	(3)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );		(до C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );	(4)	(с C++17)

Ищет последнее вхождение последовательности [s_first, s_last) в диапазоне [first, last).

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

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

2,4) То же, что и (1,3), но выполняется в соответствии с policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

Параметры

first, last	-	диапазон элементов для проверки
s_first, s_last	-	диапазон элементов для поиска
policy	-	политика выполнения. Подробнее см. политика выполнения.
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 соответственно.
Требования к типу
-`ForwardIt1` должно удовлетворять требованиям LegacyForwardIterator.
-`ForwardIt2` должно удовлетворять требованиям LegacyForwardIterator.

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

Итератор, указывающий на начало последнего вхождения последовательности [s_first, s_last) в диапазоне [first, last).

Если [s_first, s_last) пусто или такая последовательность не найдена, возвращается last.

Сложность

Дано \(\scriptsize N\)N как std::distance(first1, last1) и \(\scriptsize S\)S как std::distance(first2, last2):

1,2) Не более \(\scriptsize S\cdot(N-S+1)\)S·(N-S+1) сравнений с использованием operator==.

3,4) Не более \(\scriptsize S\cdot(N-S+1)\)S·(N-S+1) применений предиката p.

Исключения

Перегрузки с шаблоным параметром, именем ExecutionPolicy, сообщают об ошибках следующим образом:

Если выполнение функции, вызываемой как часть алгоритма, вызывает исключение, и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любой другой ExecutionPolicy, поведение определяется реализацией.
Если алгоритм не может выделить память, выбрасывается std::bad_alloc.

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

find_end (1)
template<class ForwardIt1, class ForwardIt2> ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last) { if (s_first == s_last) return last; ForwardIt1 result = last; while (true) { ForwardIt1 new_result = std::search(first, last, s_first, s_last); if (new_result == last) break; else { result = new_result; first = result; ++first; } } return result; }
find_end (3)
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate> ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p) { if (s_first == s_last) return last; ForwardIt1 result = last; while (true) { ForwardIt1 new_result = std::search(first, last, s_first, s_last, p); if (new_result == last) break; else { result = new_result; first = result; ++first; } } return result; }

find_end (1)

template<class ForwardIt1, class ForwardIt2>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last)
{
    if (s_first == s_last)
        return last;
    ForwardIt1 result = last;
    while (true)
    {
        ForwardIt1 new_result = std::search(first, last, s_first, s_last);
        if (new_result == last)
            break;
        else
        {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}

find_end (3)

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last,
                    BinaryPredicate p)
{
    if (s_first == s_last)
        return last;
    ForwardIt1 result = last;
    while (true)
    {
        ForwardIt1 new_result = std::search(first, last, s_first, s_last, p);
        if (new_result == last)
            break;
        else
        {
            result = new_result;
            first = result;
            ++first;
        }
    }
    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 (auto const& 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 (auto const& 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	значение возврата было неясным, если `[s_first,` `s_last)` пусто	в этом случае возвращается `last`

См. также

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

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