Итераторы более подробно рассматриваются в следующей главе.

linclude <vector> linclude <algorithm> linclude <string> linclude Generators.h linclude PrintSequence.h using namespace std;

int mainO { vector<string> vl(5); fill (vl.beginO. vl.endO. howdy ); print(vl.beginO. vl.endO. vl . ); vector<string> v2:

fill n(back inserter(v2). 7. bye ): print(v2.beginO. v2.end(). v2 ): vector<int> v3(10):

generate(v3.beginO, v3.end(). SkipGen(4.5)): print(v3.begin(). v3.end(). v3 . ); vector<int> v4:

generate n(back inserter(v4).15. URandGen(30)): print(v4.beginO. v4.end(). v4 . ); } III:-

Программа создает контейнер vector<string> заранее заданного размера. Поскольку для всех объектов string в контейнере память уже выделена, алгоритм fiU() может использовать свой оператор присваивания для замены каждого элемента вектора строкой howdy . Кроме того, используемый по умолчанию разделитель (символ перевода строки) заменяется пробелом.

Для второго контейнера vector<string> v2 начальный размер не задан, поэтому нам приходится вставлять новые элементы при помощи функции backJnserterO (вместо заполнения существующих позиций).

Функции generateQ и generate n() очень похожи на функции заполнения, но вместо константы при вызове используется генератор. В нашем примере продемонстрированы два разных генератора.

Подсчет

Во всех классах контейнеров определена функция size(), которая возвращает текущее количество элементов. Возвращаемое значение size() относится к типу difference type типа итератора (обычно ptrdiff t); в дальнейшем оно будет обозначаться IntegralValue. Следующие два алгоритма подсчитывают объекты, удовлетворяющие некоторому критерию.

IntegralValue countdnputlterator first. Inputlterator

last, const EqualityComparabies value);

Алгоритм возвращает количество элементов в интервале [firstlast), равных value

(при сравнении используется оператор ==).

IntegralValue countjf (Inputlterator first. Inputlterator last. Predicate pred);

Алгоритм возвращает количество элементов в интервале [firstlast), для которых предикат pred возвращает true.

Копирование и перестановки

Алгоритмы группы копирования и перестановки предназначены для перемещения элементов.

Outputlterator сору(Inputlterator first, Inputlterator last. Outputlterator destination):

Алгоритм копирует элементы из [first,last) в destination с использованием операции присваивания. После каждого присваивания destination инкрементиру-ется. Итератор destination не может содержаться в исходном интервале. Так как при копировании задействована операция присваивания, алгоритм не позволяет напрямую вставлять элементы в пустой контейнер или добавлять их в конец контейнера. Вместо этого в качестве итератора destination приходится применять итератор вставки insertjterator (обычно полученный функцией backjnserter() или inserterO для ассоциативных контейнеров).

В этом примере контейнер vector<char> v заполняется случайными символами (с повторениями). Затем на базе вектора v инициализируется контейнер set<char>, который содержит только один экземпляр каждого символа, встречающегося в v. Программа подсчитывает, сколько раз каждый символ встречается в векторе, и выводит полученные данные:

: СОб:Counting.срр Алгоритмы подсчета {L} Generators #include <a1gorithm> #include <functional> #include <iterator> #include <set> #include <vector> #include Generators.h #include PrintSequence.h using namespace std:

Int mainO { vector<char> v:

generate n(back inserter(v). 50. CharGenO): print(v.beginO. v.endO, v , ):

Создание множества (set) на базе символьного вектора v:

set<char> cs(v.beginO, v.endO):

typedef set<char>::iterator sci:

for(sci it = cs.beginO: it != cs.endO; it++) {

int n = count(v.beginO, v.endO, *it):

cout *it : n . :

int Ic = count if(v.begin(), v.endO.

bind2nd(greater<char>(). a)): cout \nLowercase letters: Ic endl: sort(v.beginO. v.endO): print(v.beginO. v.endO, sorted . ): } III:-

Работа алгоритма countJf() продемонстрирована на примере подсчета всех символов в нижнем регистре. Предикат создается с использованием стандартных шаблонов объектов функций bind2nd() и greater().

BidirectionalIterator2 copy backward(BidirectionalIteratorl first. BidirectionalIteratorl last. BidirectionalIterator2 destinationEnd):

Алгоритм делает то же самое, что и алгоритм сору(), но копирование элементов производится в обратном порядке. Исходный интервал [firstlast) копируется в приемник в обратном порядке, начиная с позиции destinationEnd-1. Далее итератор destinationEnd декрементируется после каждого присваивания. Приемный интервал должен содержать необходимое количество элементов (чтобы было возможно присваивание). Как и в случае с алгоритмом сору(), итератор destinationEnd не может содержаться в исходном интервале.

void reverse(BidirectionalIterator first. Bidirectional Iterator last): Outputlterator reverse copy(BidirectionalIterator first. Bidirectional Iterator last. Outputlterator destination):

Обе формы переставляют элементы интервала [firstlast) в обратном порядке. Алгоритм reverseO осуществляет перестановку на месте , а reverse copy() оставляет исходный интервал без изменений, копирует переставленные элементы в destination и возвращает итератор, установленный в позицию за концом полученного интервала.

ForwardIterator2 swap ranges(ForwardIteratorl firstl. Forwardlteratorl lastl. ForwardIterator2 first2):

Алгоритм меняет местами содержимое двух интервалов одинакового размера попарной перестановкой элементов.

void rotate(ForwardIterator first. Forwardlterator middle.

Forwardlterator last): Outputlterator rotate copy(ForwardIterator first.

Forwardlterator middle. Forwardlterator last.

Outputlterator destination):

Алгоритмы перемещают содержимое [firstmiddle) в конец интервала, а содержимое [middle,last) - в начало. Алгоритм rotate() осуществляет перестановку на месте , а rotate copy() оставляет исходный интервал без изменений, копирует измененную версию в destination и возвращает итератор, установленный в позицию за концом полученного интервала. Обратите внимание: в отличие от swap ranges(), эти алгоритмы не требуют, чтобы размеры интервалов были одинаковыми.

bool next permutation(BidirectionalIterator first,

Bidirectional Iterator last): bool next permutation(BidirectionalIterator first.

Bidirectional Iterator last. StrictWeakOrdering binary pred): bool prev permutation(BidirectionalIterator first.

Bidirectional Iterator last): bool prev permutation(BidirectionalIterator first.

Bidirectional Iterator last. StrictWeakOrdering binary pred):

Перестановкой называется уникальное упорядочение набора элементов. Если группа состоит из п уникальных элементов, в ней существует п! (п факториал) различных перестановок. На концептуальном уровне перестановки могут сортироваться по лексикографическому критерию, что позволяет использовать понятия следующей и предыдущей перестановок. Таким образом, независимо от текущего порядка следования элементов в последовательности перестановок всегда однозначно определяются следующая и предыдущая перестановки.