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

В данном примере мы реализуем консольное приложение, которое принимает некие входные данные, а затем пробует определить, что именно пользователь хочет найти, основываясь на небольшой текстовой базе данных.

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

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

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

template

class trie

{

  map tries;

public:

  template

  void insert(It it, It end_it) {

    if (it == end_it) { return; }

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

  }

  template

  void insert(const C &container) {

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

  }

  void insert(const initializer_list &il) {

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

  }

  void print(list &l) const {

    if (tries.empty()) {

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

      cout << '\n';

    }

    for (const auto &p : tries) {

      l.push_back(p.first);

      p.second.print(l);

      l.pop_back();

    }

  }

  void print() const {

    list l;

    print(l);

  }

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

  }

  template

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

  fstream infile {"db.txt"};

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

    istringstream iss {line};

    t.insert(istream_iterator{iss}, {});

  }

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

  prompt();

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

    istringstream iss {line};

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

    if (auto st (t.subtrie(istream_iterator{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