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

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

  OutputIterator
  rotate_copy (ForwardIterator sourceBeg, ForwardIterator newBeg,
               ForwardIterator sourceEnd,
               OutputIterator destBeg)

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

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

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

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

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

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

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

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

//---------------------------------------------------------------------------

#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()
{

  set<int> coll;

  INSERT_ELEMENTS(coll,1,9);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Вывод элементов с циклическим сдвигом на одну позицию влево
  set<int>::iterator pos = coll.begin();
  advance(pos,1);
  cout << ToRus("Вывод элементов с циклическим сдвигом на одну позицию влево:\n");
  rotate_copy(coll.begin(),                     // Начало источника
              pos,                              // Новый первый элемент
              coll.end(),                       // Конец источника
              ostream_iterator<int>(cout," ")); // Приемник
  cout << endl;

  // Вывод элементов с циклическим сдвигом на две позиции вправо
  pos = coll.end();
  advance(pos,-2);
  cout << ToRus("Вывод элементов с циклическим сдвигом на две позиции вправо:\n");
  rotate_copy(coll.begin(),                     // Начало источника
              pos,                              // Новый первый элемент
              coll.end(),                       // Конец источника
              ostream_iterator<int>(cout," ")); // Приемник
  cout << endl;

  // Вывод элементов с циклическим сдвигом, в результате которого
  // элемент со значением 4 переходит в начало
  cout << ToRus("Вывод элементов с циклическим сдвигом\n
                 с перемещением 4 в начало:\n");
  rotate_copy(coll.begin(),                     // Начало источника
              coll.find(4),                     // Новый первый элемент
              coll.end(),                       // Конец источника
              ostream_iterator<int>(cout," ")); // Приемник
  cout << endl;


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

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

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

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

Рис.1. Результат выполнения приложения

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

Предыдущий шаг Содержание Следующий шаг