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. В нашем случае это
Поделиться книгой в соц сетях:
Обратите внимание, что комментарий должен быть не короче 20 символов. Покажите уважение к себе и другим пользователям!