std::find_end
| Определено в заголовочном файле <algorithm>
|
||
| template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, |
(1) | |
| template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, |
(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 &, но функция не должна модифицировать принимаемые объекты. |
| Требования к типам | ||
-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 подпоследовательность не найдена
[править] См. также
| находит первые два соседних элемента, которые равны (или удовлетворяют заданному предикату) (шаблон функции) | |
| (C++11) |
находит первый элемент, соответствущий определённым критериям (шаблон функции) |
| ищет любой элемент из набора элементов (шаблон функции) | |
| ищет несколько последовательных копий элемента в диапазоне (шаблон функции) |
