На этом шаге мы рассмотрим алгоритмы, переставляющие элементы в обратном порядке.
Перестановочные алгоритмы изменяют порядок следования элементов (но не их значения). Элементы ассоциативных контейнеров хранятся в фиксированном порядке, поэтому они не могут использоваться в качестве приемника для перестановочных алгоритмов.
Перестановка элементов в обратном порядке
Для выполнения этой операции можно использовать следующие алгоритмы:
void
reverse (BidirectionalIterator beg, BidirectionalIterator end)
OutputIterator
reverse_copy (BidirectionalIterator sourceBeg, BidirectionalIterator sourceEnd,
Outputlterator destBeg)
Алгоритм reverse() переставляет элементы интервала [beg.end) в обратном порядке.
Алгоритм reverse_copy() переставляет в обратном порядке элементы интервала [sourceBeg, sourceEnd) в процессе их копирования в приемный интервал, начинающийся с destBeg.
Алгоритмы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был заменен в ходе копирования).
Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки.
Для списков определена аналогичная функция reverse(), которая часто работает более эффективно, поскольку она меняет внутренние указатели вместо присваивания значений элементам (смотри 204 шаг).
Сложность линейная (numberOfElements обменов или numberOfELements присваиваний соответственно).
Пример использования алгоритмов reverse() и reverse_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() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Перестановка элементов в обратном порядке reverse (coll.begin(), coll.end()); PRINT_ELEMENTS(coll,"Переставили в обратном порядке:\n"); // Перестановка в обратном порядке элементов // со второго до предпоследнего reverse (coll.begin()+1, coll.end()-1); PRINT_ELEMENTS(coll,"Перестановка в обратном порядке\n со второго до предпоследнего:\n"); // Вывод всех элементов в обратном порядке cout << ToRus("Вывод всех элементов в обратном порядке:\n"); reverse_copy (coll.begin(), coll.end(), // Источник ostream_iterator<int>(cout," ")); // Приемник cout << endl; getch(); return 0; } //---------------------------------------------------------------------------
Результат выполнения программы выглядит так:
Рис.1. Результат выполнения приложения
Со следующего шага мы будем рассматривать циклический сдвиг элементов.
