Всё про std::search и где его применять

Привет, Хабр!

Сегодня мы рассмотрим без преувеличений один из самых недооценённых алгоритмов стандартной библиотеки — std::search. Разберёмся, как он устроен, где реально экономит процессорные тики, а где лучше заменить его на что‑то иное.

Что делает std::search

Алгоритм ищет первое вхождение подпоследовательности [s_first, s_last) в диапазоне [first, last). Если «иголка» пустая, вернётся first, если вхождения нет — last. В базовой форме сравнение производится через operator==; при необходимости можно подставить предикат или целый поисковик. С C++20 почти все перегрузки search стали constexpr, так что теперь алгоритм доступен даже в static_assert‑ах.

Сложность в лобовом случае не радует: максимум N × S сравнений, где N = distance(first, last), S = distance(s_first, s_last) — типичная квадратика. Поэтому важно понимать, в каких ситуациях это приемлемо, а где надо выкатывать более хитрые searcher‑ы или вообще другой алгоритм.

Обзор всех перегрузок

Последняя перегрузка — отлична при больших паттернах. В стандарт поставили три searcher‑а: default_searcher (наивный), boyer_moore_searcher и boyer_moore_horspool_searcher. Они живут в <functional> и требуют C++17. На длинных строках ускорение в несколько раз — норма.

Базовый пример: простой поиск подстроки

#include <algorithm> #include <string_view> #include <iostream>  bool contains(std::string_view haystack, std::string_view needle) {     return std::search(haystack.begin(), haystack.end(),                        needle.begin(),  needle.end()) != haystack.end(); }  int main() {     std::string_view text  = "Для тех, кто уже знает STL";     std::cout << std::boolalpha               << contains(text, "STL")    // true               << '\n'               << contains(text, "Rust");  // false }

Кода пять строк, побочных эффектов ноль. Если «иголка» пуста, вернём begin, что иногда удобно для валидации входных данных.

Пользовательский предикат: игнорируем регистр

Часто нужно искать подстроку независимо от регистра, например "http" в строке. Это можно решить, передав в std::search пользовательский предикат:

#include <algorithm> #include <cctype> #include <string>  auto ci_equal = [](char a, char b) {     return std::tolower(static_cast<unsigned char>(a)) ==            std::tolower(static_cast<unsigned char>(b)); };  bool ci_contains(const std::string& haystack, const std::string& needle) {     return std::search(haystack.begin(), haystack.end(),                        needle.begin(),  needle.end(),                        ci_equal) != haystack.end(); }

std::search ищет подпоследовательность с учётом предиката, в нашем случае — сравнение символов без учёта регистра.

std::tolower требует unsigned char, иначе возможен UB при работе с байтами >127 в некоторых локалях.

Производительность: когда брать boyer_moore_searcher

На больших входах (N > 1 000 и S > 3) наивный алгоритм начинает тухнуть. Boyer‑Moore пропускает существенные куски входа благодаря таблицам смещений. В моих замерах на журналируемом логе 5 МБ ускорение составило ~6× по сравнению с базовым search. Профиль был чистый: всё упиралось в memcmp вместо каскада сравнений символов.

Пример:

#include <algorithm> #include <functional> #include <string_view>  std::size_t bm_find(std::string_view haystack, std::string_view needle) {     using searcher = std::boyer_moore_searcher<         std::string_view::iterator, std::string_view::iterator>;      auto it = std::search(haystack.begin(), haystack.end(),                           searcher(needle.begin(), needle.end()));     return it == haystack.end() ? std::string_view::npos                                 : std::distance(haystack.begin(), it); }

Создавать searcher лучше один раз и переиспользовать, если шаблон повторяется.

Параллельный поиск

С C++17 к большинству алгоритмов, включая search, добавили перегрузки с ExecutionPolicy. На десктопе параллельная версия даёт профит, если:

1. Размер входа измеряется мегабайтами.

2. У вас не монолитная строка, а, скажем, std::vector<int> с тяжёлым предикатом.

3. Вы готовы к оверхеду синхронизации.

#include <algorithm> #include <execution> #include <vector>  auto it = std::search(std::execution::par_unseq,                       data.begin(), data.end(),                       pattern.begin(), pattern.end());

Если предикат не свободен от побочных эффектов, параллельный запуск — запретная зона. В противном случае получите гонки и весёлый undefined behaviour.

ranges::search

С C++20 к нам пришли ranges. Функция‑объект std::ranges::search возвращает std::ranges::subrange, что избавляет от гимнастики с distance:

#include <ranges> #include <string_view>  auto sub = std::ranges::search(haystack, needle); if (!sub.empty()) {     // sub.begin() даёт позицию }

ranges‑вариант пока не поддерживает поисковые объекты типа boyer_moore_searcher. Если нужен максимум скорости,то просто остаёмся на классическом API.

Кейс 1: валидация бинарного протокола

Когда пишем протокол поверх TCP, полезно быстро находить стартовый маяк пакета вроде 0xDE,0xAD,0xBE,0xEF. Код предельно прямолинеен:

bool has_magic(const std::vector<std::uint8_t>& buf) {     constexpr std::uint8_t magic[] {0xDE, 0xAD, 0xBE, 0xEF};     auto it = std::search(buf.begin(), buf.end(),                           std::begin(magic), std::end(magic));     return it != buf.end(); }

Гарантий по выравниванию не нужно, потому что работаем через итераторы, а сравнение идёт байт к байту.

Кейс 2: сканирование лога mmap-ом

Если лог большой, память экономим за счёт mmap. Ищем строку «ERROR»:

#include <fcntl.h> #include <sys/mman.h> #include <algorithm> #include <string_view>  void scan_log(const char* path) {     int fd = open(path, O_RDONLY);     off_t size = lseek(fd, 0, SEEK_END);     char* map = static_cast<char*>(mmap(nullptr, size, PROT_READ,                                         MAP_PRIVATE, fd, 0));     std::string_view log{map, static_cast<std::size_t>(size)};     auto it = std::search(log.begin(), log.end(),                           "ERROR", "ERROR" + 5);     if (it != log.end()) {         // нашли проблему, репортим     }     munmap(map, size);     close(fd); }

Файловый ввод‑вывод мы свели к нескольким системным вызовам, всё остальное — чистый std::search.

Кейс 3: фильтрация HTTP-заголовков

Зачастую нужно выбросить запросы с запрещёнными заголовками. С код типа strcasestr давно не катит; пишем на C++:

#include <string_view> #include <algorithm>  bool contains_header(std::string_view request,                      std::string_view header) {     auto pred = [](char a, char b)     {         return std::tolower(static_cast<unsigned char>(a)) ==                std::tolower(static_cast<unsigned char>(b));     };      return std::search(request.begin(), request.end(),                        header.begin(), header.end(),                        pred) != request.end(); }

Функция не аллоцирует память, не ломает константность буфера и прозрачна для санитайзеров.

Некоторые проблемы

Первое, c чем регулярно сталкиваются: «иголка» размером в один элемент и пустой диапазон. Для одиночного байта выгоднее сразу брать std::find, а не тянуть на сцену весь search. Плюс не забываем, что пустая подпоследовательность по стандарту возвращает first; если ваши инварианты этого не ждут, отладка превратится в квест.

Вторая группа проблем касается контекста исполнения. std::search работает с байтами, поэтому для UTF-8 нужен слой декодирования или специализированная библиотека. На коротких паттернах Boyer‑Moore теряет преимущество из‑за стоимости предобработки — порог имеет смысл измерять профилем. И параллельный запуск с предикатом, зависящим от I/O, обнуляет потенциальный выигрыш и рискует привести к гонкам; в таких сценариях остаёмся на последовательной версии.

---

Итоги

std::search — рабочий инструмент для:

• линейного сканирования буферов;

• навигации по mmap‑файлам без копий;

• быстрой фильтрации потока данных;

• построения кастомных поисков с нулевой аллокацией.

Выбирайте перегрузку под задачу: наивный поиск для мелочи, Boyer‑Moore для тяжёлых строк, par_unseq для гигабайтных массивов, ranges::search для адекватного и современного кода.

Если вы уже знакомы с C++ и хотите проверить свои знания, приглашаем вас пройти тестирование. Это возможность оценить свои текущие навыки и углубить понимание ключевых аспектов языка.

Также предлагаем вам присоединиться к открытым урокам:

1. Оптимизация производительности на C++ — 6 августа в 20:00. Разберемся, как улучшить скорость работы ваших приложений на C++.

2. Контейнеры C++ — 20 августа в 20:00. Узнаем, какие контейнеры наиболее эффективны для разных задач и как их правильно использовать.

Чтобы узнать больше о курсах по C++ и получить доступ к записям открытых уроков, переходите в телеграм‑бот.