□ реализация генератора подсказок при поиске с помощью префиксных деревьев;

□ реализация формулы преобразования Фурье с применением численных алгоритмов STL;

□ определение ошибки суммы двух векторов;

□ реализация отрисовщика множества Мандельброта в ASCII;

□ создание собственного алгоритма split;

□ создание полезных алгоритмов на основе стандартных — gather;

□ удаление лишних пробельных символов между словами;

□ компрессия и декомпрессия строк. 

Введение

В предыдущей главе мы рассмотрели базовые алгоритмы STL и выполнили с их помощью простые задания, чтобы понять, как работать с типичным интерфейсом библиотеки: большая часть ее алгоритмов в качестве входных и выходных параметров принимает один или более диапазонов данных в виде пар итераторов. Они зачастую также принимают функции-предикаты, пользовательские функции сравнения или же функции преобразования. В конечном счете они в основном возвращают итераторы, поскольку их можно передать другим алгоритмам.

Хотя программисты стремятся делать алгоритмы STL минимального размера, в то же время интерфейсы они стараются разрабатывать максимально обобщенными. Это позволяет использовать код повторно, но он не всегда хорошо выглядит. Опытный разработчик С++, знающий все алгоритмы, быстрее прочитает код других людей, если они пытались выразить большинство своих идей с помощью алгоритмов STL. Мозг программиста скорее проанализирует название хорошо известного алгоритма, чем поймет сложный цикл, выполняющий ту же задачу несколько иным образом.

К этому моменту вы уже научились использовать структуры данных STL настолько интуитивно, что можете обходиться без указателей, необработанных массивов и других устаревших структур. Следующим шагом будет более глубокое изучение алгоритмов STL, чтобы вы поняли, как обойтись без сложных циклов, выражая их в терминах популярных алгоритмов STL. Это позволит значительно повысить ваш уровень, поскольку код станет более коротким, удобочитаемым и обобщенным, а также не будет привязан к структурам данных. Вы практически всегда можете избежать написания циклов вручную и взять код алгоритма из пространства имен и std, но иногда это приводит к тому, что ваш код начинает выглядеть странно. Мы не станем разбираться, какой код выглядит странно, а какой — нет, просто рассмотрим возможные варианты.

В этой главе мы применим алгоритмы STL необычным способом, чтобы исследовать новые горизонты и увидеть, как решать отдельные задачи с помощью современного С++. Кроме того, мы реализуем собственные алгоритмы, которые можно будет легко объединить с существующими структурами данных и другими алгоритмами, разработанными аналогичным способом. Затем мы объединим имеющиеся алгоритмы STL, чтобы получить новые алгоритмы, которых еще не существует. Такие объединенные алгоритмы позволяют создавать более сложные алгоритмы, но при этом они остаются относительно короткими и читабельными. Еще мы узнаем, почему именно алгоритмы STL считаются «аккуратными» и пригодными для многократного использования. Мы сможем принимать наилучшие решения, только рассмотрев все варианты. 

Реализуем класс префиксного дерева с использованием алгоритмов STL

Так называемая структура данных префиксного дерева представляет собой интересный способ хранить данные так, чтобы по ним было легко выполнить поиск. При разбиении предложений на списки слов вы зачастую можете объединить первые несколько слов, одинаковых в каждом предложении.

Взглянем на рис. 6.1, где предложения hi how are you и hi how do you do сохранены в древоподобной структуре. В этом случае одинаковыми являются слова hi how, а затем предложения различаются и разветвляются, как дерево.

Поскольку структура данных префиксного дерева объединяет общие префиксы, она также называется деревом префиксов. Такую структуру нетрудно реализовать с помощью средств, предлагаемых библиотекой STL. Этот раздел посвящен реализации собственного класса префиксного дерева.

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

В данном примере мы реализуем собственное дерево префиксов с помощью структур данных и алгоритмов, предлагаемых в библиотеке STL.

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

#include <iostream>

#include <optional>

#include <algorithm>

#include <functional>

#include <iterator>

#include <map>

#include <vector>

#include <string>

using namespace std;

2. Вся программа посвящена префиксному дереву, для которого нужно реализовать собственный класс. В нашей реализации данное дерево, по сути, является рекурсивным ассоциативным массивом, содержащим ассоциативные массивы. Каждый узел дерева содержит подобный массив, в котором соотносятся объект, имеющий тип T, и следующий узел префиксного дерева:

template <typename T> class trie

{

  map<T, trie> tries;

3. Код для добавления новых последовательностей элементов выглядит довольно просто. Пользователь предоставляет пару итераторов (начальный и конечный), и мы проходим по ним рекурсивно. Если он ввел данные {1, 2, 3}, то мы ищем значение 1 в поддереве, а затем ищем значение 2 в следующем поддереве, чтобы получить поддерево для значения 3. Какое-то из этих поддеревьев, ранее не существовавшее, будет добавлено с помощью оператора [] контейнера std::map.

public:

  template <typename It>

  void insert(It it, It end_it) {

    if (it == end_it) { return; }

    tries[*it].insert(next(it), end_it);

  }

4. Для удобства определим также отдельные функции, они дают пользователю возможность получить контейнер элементов, которые будут автоматически опрошены на предмет итераторов:

  template <typename C>

  void insert(const C &container) {

    insert(begin(container), end(container));

  }

5. Чтобы позволить пользователю написать конструкцию my_trie.insert({"a", "b", "c"});, мы должны немного помочь компилятору вывести все типы из данной строки, поэтому добавляем функцию, которая перегружает интерфейс insert параметром типа initializer_list:

  void insert(const initializer_list<T> &il) {

    insert(begin(il), end(il));

  }

6. Мы также хотим видеть содержимое дерева, поэтому нужна функция print. Для вывода содержимого дерева на экран можно выполнить поиск в глубину. На пути от корневого узла к первому листу мы записываем все элементы с полезной нагрузкой, которые мы уже встречали. Таким образом, мы получим полную последовательность, как только достигнем листа, и вывести ее на экран будет нетрудно. Мы видим, что достигли листа, когда функция tries.empty() возвращает значение true. После рекурсивного вызова функции print мы снова выталкиваем последний элемент с полезной нагрузкой.

  void print(vector<T> &v) const {

    if (tries.empty()) {

      copy(begin(v), end(v), ostream

          _iterator<T>{cout, " "});

      cout << 'n';

    }

    for (const auto &p : tries) {

      v.push_back(p.first);

      p.second.print(v);

      v.pop_back();

    }

  }