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`, если элементы следует считать равными. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&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₁ — std::distance(first1, last1), а \(\scriptsize N_2\)N₂ — std::distance(first2, last2):

1) Не более \(\scriptsize N_2\cdot(N_1-N_2+1)\)N₂⋅(N₁-N₂+1) сравнений с помощью operator==.

2) Не более \(\scriptsize N_2\cdot(N_1-N_2+1)\)N₂⋅(N₁-N₂+1) применений p.

3) \(\scriptsize \mathcal{O}(N_2\cdot(N_1-N_2+1))\)𝓞(N₂⋅(N₁-N₂+1)) сравнений с помощью operator==.

4) \(\scriptsize \mathcal{O}(N_2\cdot(N_1-N_2+1))\)𝓞(N₂⋅(N₁-N₂+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; }

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)

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