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

Базовые версии этих алгоритмов работают "на месте", т.е. они реорганизуют элементы непосредственно исходной последовательности. Три алгоритма изменения порядка предоставляют копирующие версии. Они записывают переупорядоченные значения в получающую последовательность, а не непосредственно в исходную. Для получающей последовательности этим алгоритмам требуются итераторы вывода .

Эти алгоритмы переупорядочивают исходную последовательность. Им необходимы по крайней мере прямые итераторы .

remove(beg, end, val)

remove_if(beg, end, unaryPred)

remove_copy(beg, end, dest, val)

remove_copy_if(beg, end, dest, unaryPred)

"Удаляет" элементы из последовательности, записывая поверх них те элементы, которые должны быть сохранены. Удаляются те элементы, которые равны значению valили те, для которых предикат unaryPredвернул значение true. Возвращает итератор на следующий элемент после последнего удаленного.

unique(beg, end)

unique(beg, end, binaryPred)

unique_copy(beg, end, dest)

unique_copy_if(beg, end, dest, binaryPred)

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

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.

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.