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

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{iss}, {});

}

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

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

Дополнительная информация

Можно добавить в каждый узел дерева переменные-счетчики. Это позволит определить, как часто префикс встречается в некоторых входных данных. На основе этой информации можно отсортировать предположения по частоте их встречаемости, что и делают поисковики. Подсказки, возникающие при наборе текста на смартфоне, также реализованы подобным образом.

Предлагаю вам создать этот вариант генератора подсказок в качестве самостоятельного упражнения. 

Реализуем формулу преобразования Фурье с применением численных алгоритмов STL

Преобразование Фурье — это очень важная и очень известная формула в области обработки сигналов. Она была открыта примерно 200 лет назад, но с появлением компьютеров количество вариантов ее использования значительно увеличилось. Она применяется при сжатии аудио/изображений/видео, в аудиофильтрах, медицинских устройствах отображения, приложениях для телефонов, которые определяют, какая песня сейчас играет, и т.д.

Поскольку количество возможных вариантов применения данной формулы довольно велико (и не только преобразования Фурье), STL разрабатывалась так, чтобы приносить пользу и при выполнении вычислений. Преобразование Фурье — лишь один из многих примеров подобных вычислений, при этом не самый простой. Сама формула выглядит так (рис. 6.3):