Spec-Zone.ru › C++

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)
1-4) Выполняет поиск первого вхождения целевого диапазона [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)
5) Выполняет поиск в исходном диапазоне [first1, last1) с помощью searcher. Целевой диапазон обычно задаётся при создании searcher.
Стандартная библиотека предоставляет следующие поисковые объекты:
default_searcher
(C++17)
реализация поискового алгоритма стандартной библиотеки C++
(шаблон класса)
boyer_moore_searcher
(C++17)
реализация алгоритма поиска Бойера — Мура
(шаблон класса)
boyer_moore_horspool_searcher
(C++17)
реализация алгоритма поиска Бойера — Мура — Хорспула
(шаблон класса)

Параметры

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 - политика выполнения, которую следует использовать
searcher - поисковый объект, инкапсулирующий алгоритм поиска и образец для поиска
Требования к типам
-ForwardIt1, ForwardIt2 должен соответствовать требованиям LegacyForwardIterator.
-BinaryPred должен соответствовать требованиям BinaryPredicate.

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

1-4) Итератор на начало первого вхождения целевого диапазона в исходном диапазоне.
  • Если целевой диапазон пуст, возвращается first1.
  • Если целевой диапазон не встречается в исходном диапазоне, возвращается last1.
5) searcher(first, last).first

Сложность

Пусть \(\scriptsize N_1\)N1 — это std::distance(first1, last1), а \(\scriptsize N_2\)N2 — это std::distance(first2, last2):

1) Не более \(\scriptsize N_1 \cdot N_2\)N1⋅N2 сравнений с помощью operator==.
2) Не более \(\scriptsize N_1 \cdot N_2\)N1⋅N2 вызовов p.
3) \(\scriptsize \mathcal{O}(N_1 \cdot N_2)\)𝓞(N1⋅N2) сравнений с помощью operator==.
4) \(\scriptsize \mathcal{O}(N_1 \cdot N_2)\)𝓞(N1⋅N2) вызовов p.
5) Зависит от 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 условие «вхождения последовательности» было некорректным исправлено

См. также

ranges::search
(C++20)
выполняет поиск первого вхождения диапазона элементов
(объект-функция алгоритма)
search_n
выполняет поиск первого вхождения в диапазоне заданного количества последовательных копий элемента
(шаблон функции и объект-функция алгоритма)
ranges::search_n
(C++20)
find_end
находит последнюю последовательность элементов в заданном диапазоне
(шаблон функции и объект-функция алгоритма)
ranges::find_end
(C++20)
includes
определяет, является ли одна последовательность подпоследовательностью другой
(шаблон функции и объект-функция алгоритма)
ranges::includes
(C++20)
equal
определяет, совпадают ли два набора элементов
(шаблон функции и объект-функция алгоритма)
ranges::equal
(C++20)
findfind_iffind_if_not
(C++11)
находит первый элемент, удовлетворяющий заданным критериям
(шаблон функции и объект-функция алгоритма)
ranges::findranges::find_ifranges::find_if_not
(C++20)(C++20)(C++20)
lexicographical_compare
лексикографически сравнивает два диапазона
(шаблон функции и объект-функция алгоритма)
ranges::lexicographical_compare
(C++20)
mismatch
находит первую позицию, в которой два диапазона различаются
(шаблон функции и объект-функция алгоритма)
ranges::mismatch
(C++20)

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

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API