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

Сегодня мы рассмотрим без преувеличений один из самых недооценённых алгоритмов стандартной библиотеки — 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++ и получить доступ к записям открытых уроков, переходите в телеграм‑бот.