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

   
На этом шаге мы рассмотрим использование алгоритма, выполняющего циклический сдвиг элементов внутри интервала.

   
Для выполнения этой операции можно использовать следующий алгоритм:

  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. Результат выполнения приложения

   
На следующем шаге мы рассмотрим циклический сдвиг элементов при копировании.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий