C++17 STL Стандартная библиотека шаблонов

std::string уже содержит функцию find, которая решает именно эту задачу; тем не менее в этом разделе мы сконцентрируемся на функции std::search. Несмотря на то, что она применяется по большей части для строк, ее можно использовать для контейнеров всех видов. Самая интересная особенность std::search заключается в том, что, начиная с C++17, у нее есть дополнительный интерфейс, позволяющий легко заменять алгоритм поиска. Эти алгоритмы оптимизированы, и пользователь может выбрать любой из них в зависимости от варианта применения. Вдобавок мы могли бы реализовать собственные алгоритмы поиска и подключить их в функцию std::search.

Как это делается

В этом примере мы воспользуемся новой функцией std::search для строк и опробуем ее разные вариации для объектов класса searcher.

1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:

#include

#include

#include

#include

#include

using namespace std;

2. Мы будем выводить на экран подстроки из позиций, которые вернет алгоритм поиска, поэтому реализуем соответствующую вспомогательную функцию:

template

static void print(Itr it, size_t chars)

{

  copy_n(it, chars, ostream_iterator{cout});

  cout << '\n';

}

3. Строка вида lorem-ipsum сгодится в качестве примера, мы будем искать в ней подстроку. В нашем случае таковой выступит сочетание "elitr":

int main()

{

  const string long_string {

    "Lorem ipsum dolor sit amet, consetetur"

    " sadipscing elitr, sed diam nonumy eirmod"};

  const string needle {"elitr"};

4. Старый интерфейс std::search принимает начальный/конечный итераторы для строки, внутри которой мы будем искать конкретную подстроку. Он возвращает итератор, указывающий на подстроку, которую смог найти. Если поиск не удался, то он вернет конечный итератор:

  {

    auto match (search(begin(long_string), end(long_string),

                       begin(needle), end(needle)));

    print(match, 5);

}

5. Версия функции std::search, предлагаемая в C++17, принимает не две пары итераторов, а одну (начальный/конечный) и объект поиска. Объект std::default_searcher принимает пару итераторов для подстроки, которую мы ищем в более крупной строке:

  {

    auto match (search(begin(long_string), end(long_string),

        default_searcher(begin(needle), end(needle))));

    print(match, 5);

  }

6. Суть этого изменения заключается в том, что так проще сменить алгоритм поиска. Объект std::boyer_moore_searcher использует поисковый алгоритм Бойера — Мура, чтобы выполнять поиск несколько быстрее:

  {

    auto match (search(begin(long_string), end(long_string),

         boyer_moore_searcher(begin(needle),

                              end(needle))));

    print(match, 5);

  }

7. В библиотеке STL версии C++17 появились три разные реализации поискового объекта. Третья реализация использует алгоритм Бойера—Мура—Хорспула.

  {

    auto match (search(begin(long_string), end(long_string),

        boyer_moore_horspool_searcher(begin(needle),

                                      end(needle))));

    print(match, 5);

  }

}

8. Скомпилируем и запустим программу. Если все работает правильно, то мы должны увидеть несколько одинаковых строк:

$ ./pattern_search_string

elitr

elitr

elitr

elitr

Как это работает

Мы воспользовались четырьмя разными способами применения функции std::search, чтобы получить одинаковые результаты. Какая функция больше подходит для конкретной ситуации?

Предположим, что наша большая строка, в которой мы будем искать шаблон, называется s, а сам шаблон — p. Тогда выражения std::search(begin(s), end(s), begin(p), end(p)); и std::search(begin(s), end(s), default_searcher(begin(p), end(p)); станут делать одно и то же.

Другие поисковые объекты функций реализуют более сложные алгоритмы поиска:

□ std::default_searcher — выполняет переадресацию к устаревшей реализации std::search;

□ std::boyer_moore_searcher — использует поисковый алгоритм Бойера — Мура;