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

В этом примере мы создадим небольшой словарь, в котором английские слова соотносятся с их переводом на немецкий язык, и поместим их в структуры std::deque. Программа считает словари из файла и стандартного потока ввода, а затем выведет один большой объединенный словарь в стандартный поток вывода.

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

#include

#include

#include

#include

#include

#include

#include

using namespace std;

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

using dict_entry = pair;

3. Выведем данные пары на консоль и считаем их с пользовательского ввода, поэтому нужно перегрузить операторы << и >>:

namespace std {

  ostream& 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;