class="empty-line"/>
7. Рекурсивная функция print передает ссылку на выводимый на экран список элементов, но пользователь должен вызывать ее без всяких параметров. Поэтому определяем функцию print без параметров, в которой создается вспомогательный объект списка:
void print() const {
vector<T> v;
print(v);
}
8. Теперь, когда мы научились создавать деревья и выводить их на экран, может понадобиться выполнить поиск по поддеревьям. Идея заключается в следующем: если дерево содержит последовательности наподобие {a,b,c} {a,b,d,e} и мы передаем ему последовательность {a,b} для поиска, то поиск вернет поддерево, которое содержит части {c} и {d, e}. При обнаружении поддерева возвращаем ссылку const на нее. Существует вероятность того, что такого поддерева не существует, если дерево не содержит искомой последовательности. В подобных случаях все равно нужно что-то вернуть. Здесь пригодится функция std::optional, поскольку можно вернуть пустой необязательный объект при отсутствии совпадения.
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);
}
9. Аналогично методу insert предоставляем версию метода subtrie с одним параметром, которая автоматически принимает итераторы из входного контейнера:
template <typename C>
auto subtrie(const C &c) {
return subtrie(begin(c), end(c));
}
};
10. На этом все. Воспользуемся нашим новым классом trie в функции main, создав экземпляр класса trie, работающего с объектами класса std::string, и заполнив его каким-нибудь содержимым:
int main()
{
trie<string> t;
t.insert({"hi", "how", "are", "you"});
t.insert({"hi", "i", "am", "great", "thanks"});
t.insert({"what", "are", "you", "doing"});
t.insert({"i", "am", "watching", "a", "movie"});
11. Сначала выведем на экран все дерево:
cout << "recorded sentences:n";
t.print();
12. Затем получим поддерево для всех входных предложений, которые начинаются со слова "hi", и выведем их на экран:
cout << "npossible suggestions after "hi":n";
if (auto st (t.subtrie(initializer_list<string>{"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 <typename It>
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 <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);
}
Данный код, по сути, строится вокруг выражения auto found (tries.find(*it));.
Вместо того чтобы искать следующий по глубине узел дерева с помощью оператора ([]), мы применяем метод find. Если бы мы использовали для поиска оператор [], то дерево создавало бы отсутствующие элементы — совсем не то, что нужно! (Кстати, попробуйте сделать это. Метод класса является константным, вследствие чего такой подход невозможен. Это поможет вам избежать некоторых ошибок.)
Еще одной непонятной деталью является возвращаемый тип optional<reference_wrapper<const trie>>. В качестве оболочки мы выбрали std::optional, поскольку есть вероятность, что такого поддерева во входной последовательности нет. Если мы передаем только последовательность "hello my friend", то последовательность "goodbye my friend" не будет существовать. В таких случаях мы просто возвращаем {}, что передает вызывающей стороне пустой необязательный объект. Это все еще не объясняет, почему мы используем reference_wrapper вместо optional<const trie &>. Идея заключается в том, что необязательному экземпляру, имеющему переменную-член с типом trie&, нельзя повторно присвоить значение и поэтому код не скомпилируется. Реализация ссылки с помощью reference_wrapper приведет к тому, что у вас появится возможность присваивать значения объектам повторно.
Создаем генератор поисковых подсказок с помощью префиксных деревьев
Когда вы вводите некие символы в поисковик, интерфейс зачастую пытается определить, как будет выглядеть весь поисковый запрос. Эти догадки зачастую основываются на популярных запросах. Иногда подобные догадки выглядят довольно забавно, поскольку оказывается, что люди вводят в поисковик странные запросы (рис. 6.2).
В этом разделе мы используем класс trie, который реализовали в предыдущем примере, и создадим небольшой генератор подсказок, всплывающих при поиске.
Как это делается
В данном примере мы реализуем консольное приложение, которое принимает некие входные данные, а затем пробует определить, что именно пользователь хочет найти, основываясь на небольшой текстовой базе данных.
1. Как и всегда, сначала указываем, что включаем заголовочные файлы, а также объявляем об использовании пространства
