Язык программирования C++. Пятое издание

Переупорядочивающие алгоритмы, использующие двунаправленные итераторы

Поскольку эти алгоритмы обрабатывают исходную последовательность в обратном порядке, им необходимы двунаправленные итераторы.

reverse(beg, end)

reverse_copy(beg, end, dest)

Меняет порядок элементов последовательности на обратный. Алгоритм reverse() возвращает тип void, а алгоритм reverse_copy() возвращает итератор, принимающей последовательности на элемент, который расположен за последним скопированным.

Переупорядочение алгоритмов с помощью итераторов прямого доступа

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

random_shuffle(beg, end)

random_shuffle(beg, end, rand)

shuffle(beg, end, Uniform_rand)

Осуществляет перестановку элементов исходной последовательности в случайном порядке. Перетасовывает элементы в исходной последовательности. Вторая версия получает вызываемый объект, получающий положительное целочисленное значение и возвращающий случайное целое число в диапазоне от нуля до за данного значения с равномерным распределением. Третий аргумент должен отвечать требованиям равномерного генератора случайных чисел (см. раздел 17.4). Все три версии возвращают тип void.

А.2.7. Алгоритмы перестановки

Алгоритмы перестановки осуществляют лексикографические перестановки последовательности. Эти алгоритмы переупорядочивают элементы так, чтобы получить лексикографически следующую или предыдущую перестановку заданной последовательности. Они возвращают логическое значение, означающее, была ли осуществлена следующая или предыдущая перестановка.

Чтобы лучше понять смысл следующей или предыдущей лексикографической перестановки, рассмотрим такую последовательность из трех символов: abc. У этой последовательности есть шесть возможных вариантов перестановки: abc, acb, bac, bca, cab и cba. Эти варианты перестановки перечислены в лексикографическом порядке на основании оператора "меньше". Таким образом, вариант перестановки abc будет первым, поскольку его первый элемент меньше или равен первому элементу любого другого варианта перестановки, а ее второй элемент меньше, чем у любого другого варианта с тем же первым элементом. Точно так же acb — следующий вариант перестановки, поскольку он начинается с символа а, который меньше первого элемента любого из остальных вариантов перестановки. Варианты перестановки, начинающиеся с b, располагаются перед таковыми, начинающимися с c.

Для каждого описанного выше варианта перестановки можно выяснить, какой из них должен располагаться прежде, а какие после него. Например, варианте перестановки bca можно сказать, что предыдущим для нее будет вариант bac, а следующим — cab. Для варианта abc нет предыдущего, а для варианта cba — последующего варианта перестановки.

Эти алгоритмы подразумевают, что элементы в последовательности уникальны. Таким образом, алгоритмы подразумевают, что никакие два элемента последовательности не имеют одинакового значения.

Для осуществления перестановки нужна возможность перебора последовательности вперед и назад, поэтому им требуются двунаправленные итераторы.

is_permutation(beg1, end1, beg2)

is_permutation(beg1, end1, beg2, binaryPred)

Алгоритмы возвращают значение true, если во второй последовательности есть вариант перестановки с тем же набором элементов, что и в первой последовательности, для которой элементы в варианте перестановки и в исходной последовательности равны. Первая версия сравнивает элементы, используя оператор ==; вторая использует заданный предикат binaryPred.

next_permutation(beg, end)

next_permutation(beg, end, comp)

Если последовательность уже находится в последнем варианте перестановки, алгоритм next_permutation() переупорядочивает последовательность так, чтобы она соответствовала самой младшей версии, и возвращает значение false. В противном случае последовательность преобразуется в следующий вариант перестановки и возвращает значение true. Первая версия использует для сравнения элементов оператор < типа элемента, а вторая — указанную функцию сравнения.

prev_permutation(beg, end)

prev_permutation(beg, end, comp)

Подобен алгоритму next_permutation(), но преобразует последовательность в предыдущую версию перестановки. Если текущая версия является самой младшей, переупорядочивает последовательность в самую старшую и возвращает значение false.

А.2.8. Алгоритмы набора для отсортированных последовательностей