& operator<<(ostream &os, const dict_entry p)
{
return os << p.first << " " << p.second;
}
istream& operator>>(istream &is, dict_entry &p)
{
return is >> p.first >> p.second;
}
}
4. Вспомогательная функция, принимающая любые объекты потока ввода, поможет создать словарь. Она встраивает экземпляр контейнера
std::deque
, состоящий из записей словаря, которые будут считываться из потока ввода до тех пор, пока тот не опустеет. Прежде чем вернуть контейнер, отсортируем его:
template
deque from_instream(IS &&is)
{
deque d {istream_iterator{is}, {}};
sort(begin(d), end(d));
return d;
}
5. Создадим два отдельных словаря на основе разных потоков ввода. Один будет получен из файла
dict.txt
— мы предполагаем, что он существует. Он содержит пары слов, размещенные построчно. Другой поток — это стандартный поток ввода.
int main()
{
const auto dict1 (from_instream(ifstream{"dict.txt"}));
const auto dict2 (from_instream(cin));
6. С помощью вспомогательной функции
from_instream
мы уже отсортировали оба словаря и теперь можем передать их алгоритму std::merge
. Он принимает два входных диапазона данных, определенных с помощью пар итераторов ввода/вывода. Вывод будет показан на консоли пользователя.
merge(begin(dict1), end(dict1),
begin(dict2), end(dict2),
ostream_iterator{cout, "\n"});
}
7. Мы уже можем скомпилировать программу, но перед запуском следует создать файл
dict.txt
, содержащий какие-нибудь строки. Заполним его английскими словами и их переводом на немецкий язык:
car auto
cellphone handy
house haus
8. Теперь запустим программу и передадим в стандартный поток ввода пары английских и немецких слов. В результате мы получим объединенный и отсортированный словарь, который содержит данные из обоих источников. Можно создать для него новый файл словаря.
$ echo "table tisch fish fisch dog hund" | ./dictionary_merge
car auto
cellphone handy
dog hund
fish fisch
house haus
table tisch
Как это работает
Алгоритм
std::merge
принимает две пары начальных и конечных итераторов, обозначающие входные диапазоны данных. Эти диапазоны должны быть отсортированы. Пятый параметр — итератор вывода, который принимает поступающие элементы во время слияния.Кроме того, существует вариант алгоритма, который называется
std::inplace_merge
. Он делает то же самое, что и предыдущий, но не нуждается в итераторе вывода, поскольку работает на месте, о чем можно догадаться из имени. Он принимает три параметра: начальный итератор, итератор для середины и конечный итератор. Эти итераторы должны ссылаться на данные в одной структуре. Итератор для середины является одновременно конечным итератором для первого диапазона данных и начальным итератором для второго диапазона. Это значит, что алгоритм работает с одним диапазоном данных, который на самом деле состоит из двух диапазонов, размещенных один за другим, например {A,C,B,D}
. Первый поддиапазон — {A,C}
, а второй — {B,D}
. Алгоритм std::inplace_merge
может объединить оба диапазона в одной структуре данных, что приведет к результату {A,B,C,D}
.Глава 6Сложные случаи использования алгоритмов STL
В этой главе:
□ реализация класса префиксного дерева с использованием алгоритмов STL;
□ реализация генератора подсказок при поиске с помощью префиксных деревьев;
□ реализация формулы преобразования Фурье с применением численных алгоритмов STL;
□ определение ошибки суммы двух векторов;
□ реализация отрисовщика множества Мандельброта в ASCII;
□ создание собственного алгоритма
split
;□ создание полезных алгоритмов на основе стандартных —
gather
;□ удаление лишних пробельных символов между словами;
□ компрессия и декомпрессия строк.
Введение
В предыдущей главе мы рассмотрели базовые алгоритмы STL и выполнили с их помощью простые задания, чтобы понять, как работать с типичным интерфейсом библиотеки: большая часть ее алгоритмов в качестве входных и выходных параметров принимает один или более диапазонов данных в виде пар итераторов. Они зачастую также принимают функции-предикаты, пользовательские функции сравнения или же функции преобразования. В конечном счете они в основном возвращают итераторы, поскольку их можно передать другим алгоритмам.
Хотя программисты стремятся делать алгоритмы STL минимального размера, в то же время интерфейсы они стараются разрабатывать максимально обобщенными. Это позволяет использовать код повторно, но он не всегда хорошо выглядит. Опытный разработчик С++, знающий все алгоритмы, быстрее прочитает код других людей, если они пытались выразить большинство своих идей с помощью алгоритмов STL. Мозг программиста скорее проанализирует название хорошо известного алгоритма, чем поймет сложный цикл, выполняющий ту же задачу несколько иным образом.
К этому моменту вы уже научились использовать структуры данных STL настолько интуитивно, что можете обходиться без указателей, необработанных массивов и других устаревших структур. Следующим шагом будет более глубокое изучение алгоритмов STL, чтобы вы поняли, как обойтись без сложных циклов, выражая их в терминах популярных алгоритмов STL. Это позволит значительно повысить ваш уровень, поскольку код станет более коротким, удобочитаемым и обобщенным, а также не будет привязан к структурам данных. Вы практически всегда можете избежать написания циклов вручную и взять код алгоритма из пространства имен и std, но иногда это приводит к тому, что ваш код начинает выглядеть странно. Мы не станем разбираться, какой код выглядит странно, а какой — нет, просто рассмотрим возможные варианты.
В этой главе мы применим алгоритмы STL необычным способом, чтобы исследовать новые горизонты и увидеть, как решать отдельные задачи с помощью современного С++. Кроме того, мы реализуем собственные алгоритмы, которые можно будет легко объединить с существующими структурами данных и другими алгоритмами, разработанными аналогичным способом. Затем мы объединим имеющиеся алгоритмы STL, чтобы получить новые алгоритмы, которых еще не существует. Такие объединенные алгоритмы позволяют создавать более сложные алгоритмы, но при этом они остаются относительно короткими и читабельными. Еще мы узнаем, почему именно алгоритмы STL считаются «аккуратными» и пригодными для многократного использования. Мы сможем принимать наилучшие решения, только рассмотрев все варианты.
Реализуем класс префиксного дерева с использованием алгоритмов STL
Так называемая структура данных префиксного дерева представляет собой интересный способ хранить данные так, чтобы по ним было легко выполнить поиск. При разбиении предложений на списки слов вы зачастую можете объединить первые несколько слов, одинаковых в каждом предложении.
Взглянем на рис. 6.1, где предложения
hi how are you
и hi how do you do
сохранены в древоподобной структуре. В этом случае одинаковыми являются слова hi how, а затем предложения различаются и разветвляются, как дерево.Поскольку структура данных префиксного дерева объединяет общие префиксы, она также называется деревом префиксов. Такую структуру нетрудно реализовать с помощью средств, предлагаемых библиотекой STL. Этот раздел посвящен реализации собственного класса префиксного дерева.
Как это делается
В данном примере мы реализуем собственное дерево префиксов с помощью структур данных и алгоритмов, предлагаемых в библиотеке STL.
1. Включим все заголовочные файлы применяемых частей библиотеки STL, а также объявим об использовании пространства имен