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

#include <iostream>

#include <optional>

#include <algorithm>

#include <functional>

#include <iterator>

#include <map>

#include <list>

#include <string>

#include <sstream>

#include <fstream>

using namespace std;

2. Воспользуемся реализацией из предыдущего примера:

template <typename T>

class trie

{

  map<T, trie> tries;

public:

  template <typename It>

  void insert(It it, It end_it) {

    if (it == end_it) { return; }

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

  }

  template <typename C>

  void insert(const C &container) {

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

  }

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

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

  }

  void print(list<T> &l) const {

    if (tries.empty()) {

      copy(begin(l), end(l), ostream_iterator<T>{cout, " "});

      cout << 'n';

    }

    for (const auto &p : tries) {

      l.push_back(p.first);

      p.second.print(l);

      l.pop_back();

    }

  }

  void print() const {

    list<T> l;

    print(l);

  }

  template <typename It>

  optional<reference_wrapper<const trie>>

  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);

  }

  template <typename C>

  auto subtrie(const C &c) const {

    return subtrie(begin(c), end(c));

  }

};

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

static void prompt()

{

  cout << "Next input please:n > ";

}

4. В функции main открываем текстовый файл, который играет роль нашей текстовой базы данных. Мы считываем данный файл строка за строкой и передаем эти строки в дерево:

int main()

{

  trie<string> t;

  fstream infile {"db.txt"};

  for (string line; getline(infile, line);) {

    istringstream iss {line};

    t.insert(istream_iterator<string>{iss}, {});

  }

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

  prompt();

  for (string line; getline(cin, line);) {

    istringstream iss {line};

6. Имея введенный текст, мы делаем запрос к дереву, чтобы получить поддерево. Если у нас есть такая входная последовательность в текстовом файле, то можем вывести на экран возможное продолжение поискового запроса, как делают другие поисковики. При отсутствии соответствующего поддерева просто скажем об этом пользователю:

    if (auto st (t.subtrie(istream_iterator<string>{iss}, {}));

      st) {

        cout << "Suggestions:n"; st->get().print();

    } else {

      cout << "No suggestions found.n";

    }

7. Затем снова выведем текст приглашения и подождем следующей строки от пользователя. На этом все.

    cout << "----------------n";

    prompt();

  }

}

8. Прежде чем запустить программу, следует чем-то заполнить файл db.txt. В нем может быть все что угодно, его даже не нужно сортировать. Каждая строка текста будет одной последовательностью дерева.

do ghosts exist

do goldfish sleep

do guinea pigs bite

how wrong can you be

how could trump become president

how could this happen to me

how did bruce lee die

how did you learn c++

what would aliens look like

what would macgiver do

what would bjarne stroustrup do

...

9. До запуска программы нужно создать файл db.txt. Его содержимое может выглядеть следующим образом:

hi how are you

hi i am great thanks

do ghosts exist

do goldfish sleep

do guinea pigs bite

how wrong can you be

how could trump become president

how could this happen to me

how did bruce lee die

how did you learn c++

what would aliens look like

what would macgiver do

what would bjarne stroustrup do

what would chuck norris do

why do cats like boxes

why does it rain

why is the sky blue

why do cats hate water

why do cats hate dogs

why is c++ so hard

10. Компиляция и запуск программы с последующим вводом некоторых входных данных будут выглядеть так:

$ ./word_suggestion

Next input please:

> what would

Suggestions:

aliens look like

bjarne stroustrup do

chuck norris do

macgiver do

----------------

Next input please:

> why do

Suggestions:

cats hate dogs

cats hate water

cats like boxes

----------------

Next input please:

> 

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

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

fstream infile {"db.txt"};

for (string line; getline(infile, line);) {

  istringstream iss {line};

  t.insert(istream_iterator<string>{iss}, {});

}

Цикл заполняет строку line содержимым текстового файла строка за строкой. Затем мы копируем строку в объект istringstream. Из этого объекта можно создать итератор istream_iterator, который нам еще пригодится, поскольку наше дерево принимает не только экземпляр контейнера для поиска поддеревьев, но и итераторы. Таким образом, нет нужды создавать вектор или список слов и можно непосредственно принять строку. Избежать последней части ненужных выделений памяти позволит перемещение содержимого строки в iss. К сожалению, объект типа std::istringstream не предоставляет конструктор, который принимает перемещаемые значения типа std::string. Тем не менее он скопирует свою входную строку.

При чтении пользовательских входных данных, которые нужно найти в дереве, мы применяем точно такую же стратегию, но не задействуем файловый поток ввода. Вместо этого мы прибегаем к std::cin. В нашем случае это