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

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

rotate(beg, mid, end)

rotate_copy(beg, mid, end, dest)

"Поворачивает" элементы вокруг элемента, обозначенного итератором mid. Элемент, указанный итератором mid, становится первым элементом, затем идет последовательность от mid+1до end(но не включая его), далее следует диапазон от begдо mid(но не включая его). Возвращает итератор, обозначающий элемент, который первоначально был в beg.

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

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.

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

Чтобы лучше понять смысл следующей или предыдущей лексикографической перестановки, рассмотрим такую последовательность из трех символов: 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.