std::search
Определён в заголовочном файле <algorithm> | ||
|---|---|---|
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
| (1) | (constexpr начиная с C++20) |
template< class ForwardIt1, class ForwardIt2, class BinaryPred >
ForwardIt1 search( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
BinaryPred p );
| (2) | (constexpr начиная с C++20) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
| (3) | (начиная с C++17) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class BinaryPred >
ForwardIt1 search( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
BinaryPred p );
| (4) | (начиная с C++17) |
template< class ForwardIt, class Searcher >
ForwardIt search( ForwardIt first1, ForwardIt last1,
const Searcher& searcher );
| (5) | (начиная с C++17) |
[first2, last2) в исходном диапазоне [first1, last1).p.policy.true: |
| (до C++20) |
|
| (начиная с C++20) |
[first1, last1) с помощью searcher. Целевой диапазон обычно задаётся при создании searcher.|
(C++17) | реализация поискового алгоритма стандартной библиотеки C++ (шаблон класса) |
|
(C++17) | реализация алгоритма поиска Бойера — Мура (шаблон класса) |
|
(C++17) | реализация алгоритма поиска Бойера — Мура — Хорспула (шаблон класса) |
Параметры
| first1, last1 | - | пара итераторов, определяющих исходный диапазон |
| first2, last2 | - | пара итераторов, определяющих целевой диапазон |
| p | - | бинарный предикат, возвращающий true, если элементы следует считать равными. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&b); Хотя сигнатура не обязана иметь |
| policy | - | политика выполнения, которую следует использовать |
| searcher | - | поисковый объект, инкапсулирующий алгоритм поиска и образец для поиска |
| Требования к типам | ||
-ForwardIt1, ForwardIt2 должен соответствовать требованиям LegacyForwardIterator. |
||
-BinaryPred должен соответствовать требованиям BinaryPredicate. |
||
Возвращаемое значение
1-4) Итератор на начало первого вхождения целевого диапазона в исходном диапазоне.- Если целевой диапазон пуст, возвращается
first1. - Если целевой диапазон не встречается в исходном диапазоне, возвращается
last1.
searcher(first, last).first
Сложность
Пусть \(\scriptsize N_1\)N1 — это std::distance(first1, last1), а \(\scriptsize N_2\)N2 — это std::distance(first2, last2):
p.p.searcher.Исключения
3,4) Во время выполнения:- Если временные ресурсы памяти, необходимые для распараллеливания, недоступны, выбрасывается
std::bad_alloc. - Если при доступе к объектам через аргумент алгоритма возникает неперехваченное исключение, поведение определяется политикой выполнения (для стандартных политик вызывается
std::terminate).
Возможная реализация
| поиск (1) |
|---|
template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last)
{
while (true)
{
ForwardIt1 it = first;
for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
{
if (s_it == s_last)
return first;
if (it == last)
return last;
if (!(*it == *s_it))
break;
}
++first;
}
}
|
| поиск (2) |
template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p)
{
while (true)
{
ForwardIt1 it = first;
for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
{
if (s_it == s_last)
return first;
if (it == last)
return last;
if (!p(*it, *s_it))
break;
}
++first;
}
}
|
Пример
#include <algorithm>
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>
using namespace std::literals;
bool contains(const auto& cont, std::string_view s)
{
// str.find() (or str.contains(), since C++23) can be used as well
return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
int main()
{
const auto str{"why waste time learning, when ignorance is instantaneous?"sv};
assert(contains(str, "learning"));
assert(not contains(str, "lemming"));
const std::vector vec(str.begin(), str.end());
assert(contains(vec, "learning"));
assert(not contains(vec, "leaning"));
// The C++17 overload with searchers demo:
constexpr auto quote
{
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
"do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
};
for (const auto word : {"pisci"sv, "Pisci"sv})
{
std::cout << "The string " << std::quoted(word) << ' ';
const std::boyer_moore_searcher searcher(word.begin(), word.end());
const auto it = std::search(quote.begin(), quote.end(), searcher);
if (it == quote.end())
std::cout << "not found\n";
else
std::cout << "found at offset " << std::distance(quote.begin(), it) << '\n';
}
}
Вывод:
The string "pisci" found at offset 43 The string "Pisci" not found
Отчёты об ошибках
Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.
| DR | Применён к | Опубликованное поведение | Исправленное поведение |
|---|---|---|---|
| LWG 1205 | C++98 | возвращаемое значение не было определено, если целевой диапазон пуст | в этом случае возвращается first1 |
| LWG 1338 | C++98 | поправка к отчёту LWG 1205 была применена некорректно, в результате чего возвращалось first1, если целевой диапазон не найден | в этом случае возвращается last1 |
| LWG 2150 | C++98 | условие «вхождения последовательности» было некорректным | исправлено |
См. также
|
(C++20) | выполняет поиск первого вхождения диапазона элементов (объект-функция алгоритма) |
| выполняет поиск первого вхождения в диапазоне заданного количества последовательных копий элемента (шаблон функции и объект-функция алгоритма) |
|
|
(C++20) | |
| находит последнюю последовательность элементов в заданном диапазоне (шаблон функции и объект-функция алгоритма) |
|
|
(C++20) | |
| определяет, является ли одна последовательность подпоследовательностью другой (шаблон функции и объект-функция алгоритма) |
|
|
(C++20) | |
| определяет, совпадают ли два набора элементов (шаблон функции и объект-функция алгоритма) |
|
|
(C++20) | |
|
(C++11) | находит первый элемент, удовлетворяющий заданным критериям (шаблон функции и объект-функция алгоритма) |
|
(C++20)(C++20)(C++20) | |
| лексикографически сравнивает два диапазона (шаблон функции и объект-функция алгоритма) |
|
|
(C++20) | |
| находит первую позицию, в которой два диапазона различаются (шаблон функции и объект-функция алгоритма) |
|
|
(C++20) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/search