sample(begin(v), end(v), back_inserter(samples),
sample_points, mt19937{random_device{}()});
8. С выборкой мы закончили. Остальная часть кода посвящена отображению данных. Входные данные имеют нормальное распределение, и если алгоритм выборки отработал хорошо, то полученный вектор тоже должен иметь такое же распределение. Чтобы увидеть, насколько распределение отклоняется от нормального, выведем на экран гистограмму значений:
map hist;
for (int i : samples) { ++hist[i]; }
9. Наконец, пройдем в цикле по всем элементам, чтобы вывести нашу гистограмму на экран:
for (const auto &[value, count] : hist) {
cout << setw(2) << value << " "
<< string(count, '*') << '\n';
}
}
10. После компиляции и запуска программы мы видим, что полученный вектор имеет характеристики нормального распределения (рис. 5.5):
Как это работает
Алгоритм
std::sample
— это новый алгоритм, который появился в версии С++17. Его сигнатура выглядит следующим образом:
template
class Distance, class UniformRandomBitGenerator>
OutIterator sample(InIterator first, InIterator last,
SampleIterator out, Distance n,
UniformRandomBitGenerator&& g);
Входной диапазон данных обозначается итераторами
first
и last
, в то время как out
— итератор вывода. Эти итераторы выполняют ту же функцию, что и для функции std::copy;
элементы копируются из одного диапазона в другой. Алгоритм std::sample
является особенным с той точки зрения, что копирует только часть входного диапазона, поскольку делает выборку только n
элементов. Он использует равномерное распределение внутри системы, поэтому каждая точка на графике во входном диапазоне данных может быть выбрана с одинаковой вероятностью. Выполняем перестановки во входных последовательностях
При тестировании кода, который должен работать с последовательностями входных данных, где порядок аргументов не так важен, полезно проверять, получаем ли мы одинаковый результат во всех возможных перестановках для этих входных данных. Такой тест может, например, проверять, корректно ли работает ваш собственный алгоритм сортировки.
Независимо от того, зачем нужны все перестановки для какого-то диапазона значений,
std::next_permutation
позволит это реализовать. Можно вызвать эту функцию для изменяемого диапазона, и она изменит порядок его элементов на следующую лексикографическую перестановку.
Как это делается
В данном примере мы напишем программу, которая считывает несколько строк, содержащих слова, из стандартного потока ввода, а затем применим функцию
std::next_permutation
, чтобы сгенерировать и вывести на экран все перестановки для этих строк.
1. Как и обычно, сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен
std
:
#include
#include
#include
#include
#include
using namespace std;
2. Мы начнем с вектора строк, который заполним из стандартного потока ввода. Затем отсортируем вектор:
int main()
{
vector v {istream_iterator{cin}, {}};
sort(begin(v), end(v));
3. Далее выведем содержимое вектора на консоль. Затем вызовем функцию
std::next_permutation
. Она систематически перемешивает содержимое вектора, чтобы сгенерировать перестановки этих элементов, которое мы снова выведем на экран. Вызов next_permutation
вернет значение false
, когда будет сгенерирована последняя перестановка.
do {
copy(begin(v), end(v),
ostream_iterator{cout, ", "});
cout << '\n';
} while (next_permutation(begin(v), end(v)));
}
4. Скомпилируем и запустим функцию, передав ей какие-нибудь данные:
$ echo "a b c" | ./input_permutations
a, b, c,
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
#include
#include
#include
#include
#include
#include
using namespace std;
2. Запись словаря должна состоять из симметричной пары, содержащей строки на обоих языках.
using dict_entry = pair;
3. Выведем данные пары на консоль и считаем их с пользовательского ввода, поэтому нужно перегрузить операторы
<<
и >>
:
namespace std {
ostream