class="p1">a, c, b,

b, a, c,

b, c, a,

c, a, b,

c, b, a,

Как это работает

Алгоритм std::next_permutation выглядит несколько странным. Это потому, что он принимает только пару итераторов (начальный и конечный) и возвращает значение true, если может найти следующую перестановку. В противном случае он возвращает значение false. Но что вообще означает выражение следующая перестановка?

Алгоритм, с помощью которого функция std::next_permutation находит следующий лексикографический порядок элементов, работает таким образом.

1. Найдем самое большое значение индекса i, для которого выполняется условие v[i-1] < v[i]. Если такого значения нет, то вернем значение false.

2. Теперь найдем самое большое значение индекса j, для которого выполняются условия j >= i и v[j] > v[i-1].

3. Меняем местами элементы на позициях j и i-1.

4. Изменим порядок элементов, находящихся между позицией i и концом диапазона данных, на противоположный.

5. Вернем значение true.

Отдельные порядки перестановки, которые мы получим в результате вызова этой функции, всегда будут появляться в одинаковой последовательности. Чтобы найти все возможные перестановки, мы поначалу отсортировали массив. Это было сделано потому, что если бы ввели строку "c b a", например, то алгоритм завершил бы работу немедленно, так как данная строка представляет собой последний возможный лексикографический порядок элементов.

Инструмент для слияния словарей

 Представьте, что у вас имеется отсортированный список элементов, у кого-то другого появляется другой такой же список и вы хотите обменяться этими списками друг с другом. Самая лучшая идея заключается в том, чтобы объединить оба списка. Их комбинацию нужно отсортировать, поскольку так будет проще найти конкретные элементы.

Данная операция также называется слиянием. Чтобы слить воедино два отсортированных диапазона данных, можно создать новый диапазон и заполнить его элементами из обоих списков. Для каждого перемещения элемента нужно сравнить два элемента наших входных диапазонов данных с целью выбрать самый маленький из оставшихся. В противном случае выходной диапазон не будет отсортирован. Этот процесс показан на рис. 5.6.

Алгоритм std::merge позволяет решить именно эту задачу, поэтому не придется тратить время зря. В данном разделе мы увидим, как пользоваться этим алгоритмом.

Как это делается

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

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

#include <iostream>

#include <algorithm>

#include <iterator>

#include <deque>

#include <tuple>

#include <string>

#include <fstream>

using namespace std;

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

using dict_entry = pair<string, string>;

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 <typename IS>

deque<dict_entry> from_instream(IS &&is)

{

  deque<dict_entry> d {istream_iterator<dict_entry>{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<dict_entry>{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

В этой главе:

□ реализация класса префиксного дерева с