Модифицирующие алгоритмы. Обмен интервалов

   
На этом шаге мы рассмотрим алгоритм, осуществляющий обмен интервалов.

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

  ForwardIterator2
  swap_ranges (ForwardIterator1 beg1, ForwardIterator1 end1, 
               ForwardIterator2 beg2)

   
Этот алгоритм меняет местами элементы интервала [beg1,end1) с соответствующими элементами интервала [beg2,...).

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

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

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

   
Для обмена элементов в контейнерах одного типа рекомендуется использовать функцию swap() класса контейнера, поскольку
она обычно выполняется с постоянной сложностью (смотри 199 шаг).

   
Сложность линейная (numberOfElements операций перестановки). Пример использования алгоритма swap_ranges():

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

#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> coll1;
  deque<int> coll2;

  INSERT_ELEMENTS(coll1,1,9);
  INSERT_ELEMENTS(coll2,11,23);

  PRINT_ELEMENTS(coll1,"1-я коллекция:\n");
  PRINT_ELEMENTS(coll2,"2-я коллекция:\n");

  // Элементы coll1 меняются местами с соответствующими элементами coll2
  deque<int>::iterator pos;
  pos = swap_ranges (coll1.begin(), coll1.end(),  // Первый интервал
                     coll2.begin());              // Второй интервал

  PRINT_ELEMENTS(coll1,"\n1-я коллекция:\n");
  PRINT_ELEMENTS(coll2,"2-я коллекция:\n");
  if (pos != coll2.end()) {
      cout << ToRus("Первый немодифицированный элемент: ")
           << *pos << endl;
  }

  // Зеркальный обмен трех первых элементов coll2
  // с тремя последними элементами
  swap_ranges (coll2.begin(), coll2.begin()+3,    // Первый интервал
               coll2.rbegin());                   // Второй интервал

  PRINT_ELEMENTS(coll2,"\n2-я коллекция:\n");


  getch();
  return 0;
}

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

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

   
Первый вызов swap_ranges() меняет местами элементы coll1 с соответствующими элементами соll2.
Остальные элементы соll2 не изменяются. Алгоритм swap_ ranges() возвращает позицию первого элемента, который
остался без изменений. Второй вызов меняет местами первые и последние три элемента coll2. Один из итераторов является
обратным, поэтому обмен происходит с зеркальным отображением элементов. Программа выводит следующий результат:


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

   
Со следующего шага мы начнем рассматривать присваивание.



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

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