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

12. Затем получим поддерево для всех входных предложений, которые начинаются со слова "hi", и выведем их на экран:

  cout << "\npossible suggestions after \"hi\":\n";

  if (auto st (t.subtrie(initializer_list{"hi"}));

    st) {

      st->get().print();

    }

  }

13. Компиляция и запуск программы покажет, что мы действительно получим всего два предложения, начинающихся со слова "hi ", если запросим именно это поддерево:

$ ./trie

recorded sentences:

hi how are you

hi i am great thanks

i am watching a movie

what are you doing

possible suggestions after "hi":

how are you

i am great thanks

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

Что интересно, код для вставки последовательности слов выглядит короче и проще, чем код поиска заданного слова в поддереве. Поэтому сначала рассмотрим код вставки:

template

void trie::insert(It it, It end_it) {

  if (it == end_it) { return; }

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

}

Пара итераторов it и end_it представляет собой вставляемую последовательность слов. Элемент tries[*it] выполняет поиск первого слова последовательности в поддереве, а затем с помощью конструкции .insert(next(it), end_it) мы перезапускаем ту же функцию для найденного нижнего поддерева, переместив итератор на одно слово вперед. Строка if (it == end_it) { return; } нужна для прерывания рекурсии. Пустое выражение return не делает ничего, что на первый взгляд кажется странным. Все операции вставки выполняются с привлечением выражения tries[*it]. Оператор [] контейнера std::map либо возвращает существующий элемент для заданного ключа, либо создает элемент с таким ключом. Связанное значение (соотнесенным типом в нашем примере является тип trie) создается с помощью конструктора по умолчанию. Таким образом, при поиске не известных слов мы неявно создаем новую ветвь дерева.

Поиск в поддереве выглядит более сложным, поскольку мы не можем выразить многие функции неявно:

template

optional>

subtrie(It it, It end_it) const {

  if (it == end_it) { return ref(*this); }

    auto found (tries.find(*it));

    if (found == end(tries)) { return {}; }

  return found->second.subtrie(next(it), end_it);

}

Данный код, по сути, строится вокруг выражения auto found (tries.find(*it));.

Вместо того чтобы искать следующий по глубине узел дерева с помощью оператора ([]), мы применяем метод find. Если бы мы использовали для поиска оператор [], то дерево создавало бы отсутствующие элементы — совсем не то, что нужно! (Кстати, попробуйте сделать это. Метод класса является константным, вследствие чего такой подход невозможен. Это поможет вам избежать некоторых ошибок.)

Еще одной непонятной деталью является возвращаемый тип optional>. В качестве оболочки мы выбрали std::optional, поскольку есть вероятность, что такого поддерева во входной последовательности нет. Если мы передаем только последовательность "hello my friend", то последовательность "goodbye my friend" не будет существовать. В таких случаях мы просто возвращаем {}, что передает вызывающей стороне пустой необязательный объект. Это все еще не объясняет, почему мы используем reference_wrapper вместо optional. Идея заключается в том, что необязательному экземпляру, имеющему переменную-член с типом trie&, нельзя повторно присвоить значение и поэтому код не скомпилируется. Реализация ссылки с помощью reference_wrapper приведет к тому, что у вас появится возможность присваивать значения объектам повторно. 

Создаем генератор поисковых подсказок с помощью префиксных деревьев

 Когда вы вводите некие символы в поисковик, интерфейс зачастую пытается определить, как будет выглядеть весь поисковый запрос. Эти догадки зачастую основываются на популярных запросах. Иногда подобные догадки выглядят довольно забавно, поскольку оказывается, что люди вводят в поисковик странные запросы (рис. 6.2).

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

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