Шаг 298.
Библиотека STL. Алгоритмы STL. Перестановочные алгоритмы. Циклический сдвиг элементов. Циклический сдвиг элементов при копировании

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

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

  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() в данном случае вместо вектора используется множество. Смена контейнера влечет за собой два следствия:

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


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

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




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