Пространства имён
Варианты
Действия

std::find_end

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class ForwardIt1, class ForwardIt2 >

ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,

                     ForwardIt2 s_first, ForwardIt2 s_last );
(1)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >

ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,

                     ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
(2)

Ищет последнее вхождение подпоследовательности элементов [s_first, s_last) в диапазон [first, last). Первый вариант использует operator== для сравнения элементов, второй вариант использует заданный бинарный предикат p.

Содержание

[править] Параметры

first, last - диапазон элементов для проверки
s_first, s_last - диапазон элементов для поиска
p - бинарный предикат, который возвращает ​true если элементы следует считать равными.

Определение функции предиката должно быть эквивалентно следующему:

 bool pred(const Type1 &a, const Type2 &b);

Определение не должно обязательно содержать const &, но функция не должна модифицировать принимаемые объекты.
Типы Type1 и Type2 должны быть таковы, что объекты типов ForwardIt1 и ForwardIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно.

Требования к типам
-
ForwardIt1 должен соответствовать требованиям ForwardIterator.
-
ForwardIt2 должен соответствовать требованиям ForwardIterator.

[править] Возвращаемое значение

Итератор на начало последнего вхождения подпоследовательности элементов [s_first, s_last) в диапазон [first, last).

Если такая подпоследовательность не найдена, то возвращается last. (до C++11)

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

[править] Сложность

Не больше S*(N-S+1) сравнений, где S = distance(s_first, s_last), N = distance(first, last).

[править] Возможная реализация

Первый вариант
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 (1) {
        ForwardIt1 new_result = std::search(first, last, s_first, s_last);
        if (new_result == last) {
            return result;
        } else {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}
Второй вариант
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 (1) {
        ForwardIt1 new_result = std::search(first, last, s_first, s_last, p);
        if (new_result == last) {
            return result;
        } else {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}

[править] Пример

Следующий код использует find_end() для поиска двух различных последовательностей чисел.

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    std::vector<int>::iterator result;
 
    std::vector<int> t1{1, 2, 3};
 
    result = std::find_end(v.begin(), v.end(), t1.begin(), t1.end());
    if (result == v.end()) {
        std::cout << "подпоследовательность не найдена\n";
    } else {
        std::cout << "последнее вхождение в позиции: "
                  << std::distance(v.begin(), result) << "\n";
    }
 
    std::vector<int> t2{4, 5, 6};
    result = std::find_end(v.begin(), v.end(), t2.begin(), t2.end());
    if (result == v.end()) {
        std::cout << "подпоследовательность не найдена\n";
    } else {
        std::cout << "последнее вхождение в позиции: "
                  << std::distance(v.begin(), result) << "\n";
    }
}

Вывод:

последнее вхождение в позиции: 8
подпоследовательность не найдена

[править] См. также

Ищет в диапазоне два одинаковых смежных элемента
(шаблон функции) [edit]
Находит первый элемент, удовлетворяющий определенным критериям
(шаблон функции) [edit]
Ищет в множестве элементов первое вхождение любого элемента другого множества
(шаблон функции) [edit]
Ищет в диапазоне первую последовательность n одинаковых элементов, каждый из которых равен заданному значению
(шаблон функции) [edit]