На этом шаге мы рассмотрим использование алгоритма, выполняющего циклический сдвиг элементов внутри интервала.
Для выполнения этой операции можно использовать следующий алгоритм:
void
rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end)
Производит циклический сдвиг элементов в интервале [beg,end). После вызова *newBeg становится новым первым элементом.
Перед вызовом необходимо убедиться в том, что newBeg представляет действительную позицию н интервале [beg,end); в противном случае вызов приводит к непредсказуемым последствиям.
Сложность линейная (не более numberOfElements обменов).
Пример использования алгоритма rotate():
//--------------------------------------------------------------------------- #include <vcl.h> #include <iterator> #include "algostuff.hpp" #include <conio.h> //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) { char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; } int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Циклический сдвиг на один элемент влево rotate (coll.begin(), // Начало интервала coll.begin() + 1, // Новый первый элемент coll.end()); // Конец интервала PRINT_ELEMENTS(coll,"Циклический сдвиг на один элемент влево:\n"); // Циклический сдвиг на два элемента вправо rotate (coll.begin(), // Начало интервала coll.end() - 2, // Новый первый элемент coll.end()); // Конец интервала PRINT_ELEMENTS(coll,"Циклический сдвиг на два элемента вправо:\n"); // Циклический сдвиг, в результате которого элемент со значением 4 // переходит в начало rotate (coll.begin(), // Начало интервала find(coll.begin(),coll.end(),4), // Новый первый элемент coll.end()); // Конец интервала PRINT_ELEMENTS(coll,"Циклический сдвиг c 4 вначале:\n"); getch(); return 0; } //---------------------------------------------------------------------------
Как видно из приведенного примера, циклический сдвиг влево осуществляется с положительным смещением от начала, а сдвиг вправо - с отрицательным смещением от конца. Тем не менее прибавление смещения к итератору возможно только при использовании итераторов произвольного доступа (векторы поддерживают такие итераторы). Без итераторов произвольного доступа необходима функция advance().
Результат выполнения программы выглядит так:
Рис.1. Результат выполнения приложения
На следующем шаге мы рассмотрим циклический сдвиг элементов при копировании.
