Циклический сдвиг, в результате которого элемент со значением 4 переходит в начало

rotate (coll.beginO. Начало интервала

find(coll-beginO.coll ,end() .4). Новый первый элемент coll.endO): Коней интервала

PRINT ELEMENTS(coll."4 first: ");

Как видно из приведенного примера, циклический сдвиг влево осуществляется с положительным смещением от начала, а сдвиг вправо - с отрицательным смещением от конца. Тем не менее прибавление смещения к итератору возможно только при использовании итераторов произвольного доступа (векторы поддерживают такие итераторы). Без итераторов произвольного доступа необходима функция advance() (см. далее пример применения функции rotate copy()).

Результат выполнения программы выглядит так:

coll: 123456789

one left: 234567891 two right: 9 12 3 4 5 6 7 8 4 first: 4 5 6 7 8 9 12 3

Циклический сдвиг элементов при копировании

Outputlterator

rotate copy (Forwardlterator sourceBeg. Forwardlterator newBeg, Forwardlterator sourceEnd. Outputlterator destBeg)

О Алгоритм является объединением алгоритмов сору() и rotate().

О Копирует элементы интервала [sourceBeg,sourceEnd) в приемный интервал, начинающийся с destBeg. При этом элементы циклически сдвш-аются так, что newBeg становится новым первым элементом.

О Возвращает позицию за последним скопированным элементом в приемном интервале.

О Перед вызовом необходимо убедиться в том, что newBeg представляет элемент в интервале [begend); в противном случае вызов приводит к непредсказуемым последствиям.

О Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки.

О Источник не должен перекрываться с приемником.

О Сложность линейная (не более numberOfElements обменов).

Следующая программа демонстрирует использование алгоритма rotate copy():

algo/rotate2.cpp finclude "algostuff.hpp" using namespace std:

int mainO (

set<int> coll:

INSERTJLEMENTS(C0ll.l.9) PRINT ELEMENTS(coll);

Вывод элементов с циклическим сдвигом на одну позицию влево set<int>;:iterator pos = coll.beginO; advance(pos.l); rotate copy(col 1 .beginO. pos.

coll .endO.

ostream i terator<i nt>(cout." cout « endl;

Начало источника Новый первый элемент Конец источника ")): Приемник

Вывод элементов с циклическим сдвигом на две позиции вправо роз = coll .endO: advance(pos.-2); rotate copy(col 1.begi n(). pos.

coll .endO.

ostream iterator<int>(cout." ")) cout « endl;

Начало источника

Новый первый элемент

Конец источника

Приемник

Вывод элементов с циклическим сдвигом, в результате которого элемент со значением 4 переходит в начало

rotate copy(coll .beginO.

coll.find(4). coll .endO.

ostream iterator<int>(cout. cout « endl;

Начало источника

Новый первый элемент

Конец источника

Приемник

В отличие от приведенного ранее примера для алгоритма rotate() (см. с. 380) в данном случае вместо вектора используется множество. Смена контейнера влечет за собой два следствия:

О изменение итератора должно производиться функнией advance(), поскольку двунаправленные итераторы не поддерживают оператор +;

О вместо алгоритма find() должна использоваться более эффективная функ-пия find().

Результат выполнения программы выглядит так:

123456789 2 3 4 5 6 7 8 9 1 8 9 1 2 3 4 5 6 7 4 5 6 7 8 9 1 2 3

Перестановка элементов

bool

next permutation (Bidirectionallterator beg. Bidirectionallterator end) bool

prev permutation (Bidirectionallterator beg. Bidirectionallterator end)

О Алгоритм next permutation() изменяет порядок следования элементов в интервале [heg,end) в соответствии со следующей перестановкой.

О Алгоритм prev permutation() изменяет порядок следования элементов в интервале [beg,end) в соответствии с предьщущей перестановкой.

О Оба алгоритма возвращают false, если элементы находятся в «нормальном» (лексикографическом) порядке, то есть зшорядочены по возрастанию для next permutationO или по убыванию для prev permutation(). Следовательно, для того чтобы перебрать все перестановки, нужно отсортировать элементы (по возрастанию или убыванию) и организовать цикл, который вызывает алгоритм next permutationO или prev permutation() до тех пор, пока алгоритм возвращает true.

Лексикографическая сортировка рассматривается на с. 356.

О Сложность линейная (не более numberOfElements/2 обменов).

Следующий пример показывает, как при помощи алгоритмов nexLpermutationO и prev permutationO генерируются все перестановки элементов:

algo/perml.cpp finclude "algostuff.hpp" using namespace std:

int mainO (

vector<int> coll:

INSERT ELEMENTS(col 1.1.3): PRINT ELEMENTS(coll."on entry: ");

/* Генерировать перестановки элементов до тех лор. пока они

* не будут упорядочены

* - при этом перебираются все возможные перестановки.

* - потому что в исходном состоянии

* - элементы упорядочены по возрастанию */

while (next permutat1on(coll .beginO .coll .endO)) ( PRINT ELEMENTS(coll." "):

Алгоритмы next permutation() и prev permutation() также могут использоваться для сортировки элементов в интервале - просто вызывайте их до тех пор, пока возвращаемое значение остается равным true. Впрочем, такой способ сортировки отличается очень плохой эффективностью.