Категории итераторов

Возможности итераторов не исчерпываются базовыми операциями. Конкретный состав операций, поддерживаемых итератором, зависит от внутренней структуры типа контейнера. Как обычно, STL поддерживает только те операции, которые выполняются с хорошим быстродействием. Например, если контейнер обеспечивает произвольный доступ, как векторы или деки, его итератор также сможет выполнять операции произвольного доступа, например, его можно установить сразу на пятый элемент.

Итераторы делятся на несколько категорий в зависимости от их общих возможностей. Итераторы стандартных контейнерных классов относятся к одной из двух категорий.

- Двунаправленные итераторы. Как подсказывает само название, двунаправленный итератор может перемещаться в двух направлениях: в прямом (оператор ++) и обратном (оператор --). Итераторы контейнерных классов list, set, multiset, map и multimap являются двунаправленными.

- Итераторы произвольного доступа. Итераторы произвольного доступа обладают всеми свойствами двунаправленных итераторов, но в дополнение к ним они обеспечивают произвольный доступ к элементам контейнера. В частности, поддерживаются математические операции с итераторами (по аналогии с математическими операциями над обычными указателями). Вы можете прибавлять и вычитать смещения, обрабатывать разность и сравнивать итераторы с помощью таких операторов, как < и >. Итераторы контейнерных классов vector и deque, а также итераторы строк являются итераторами произвольного доступа.

Чтобы программный код как можно меньше зависел от типа контейнера, постарайтесь по возможности избегать специальных операций с итераторами произвольного доступа. Например, следующий цикл работает с любым контейнером:

for (pos = coll.begin(); pos != coll.end(); ++pos) { …}

А этот цикл работает не со всеми контейнерами:

for (pos = coll.begin(); pos < coll.end(); ++pos) { …}

Единственное различие - наличие оператора < вместо != в условии второго цикла. Оператор < поддерживается только итераторами произвольного доступа, поэтому второй цикл не будет работать со списками, множествами и отображениями. В унифицированном коде, ориентированном на работу с любыми контейнерами, следует использовать оператор != вместо <. С другой стороны, это несколько снижает надежность кода, поскольку pos может случайно перейти в позицию за end(). Сами решайте, какая версия больше подходит для вашего случая. Выбор зависит от контекста, а иногда даже от личных предпочтений.

Чтобы избежать недопонимания, поясняем, что в этой разделе речь идёт о категориях, а не о классах итераторов. Категория определяет только возможности итераторов независимо от их типов. Согласно общей концепции STL, то есть на уровне чистой абстракции, любой объект, который ведет себя как двунаправленный итератор, является двунаправленным итератором.

Алгоритмы

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

Алгоритмы не являются функциями контейнерных классов — это глобальные функции, работающие с итераторами. У такого подхода есть одно важное достоинство: вместо того чтобы реализовывать каждый алгоритм для каждого типа контейнера, достаточно реализовать его один раз для обобщенного типа контейнера. Алгоритм может работать даже с элементами контейнеров разных типов, в том числе определенных пользователем. В конечном счете такой подход сокращает объем программного кода, делая библиотеку более мощной и гибкой.

Обратите внимание: речь идет не о парадигме объектно-ориентированного программирования, а об общей парадигме функционального программирования. Вместо того чтобы объединять данные с операциями, как в объектно-ориентированном программировании, мы разделяем их на части, взаимодействующие через некоторый интерфейс. Впрочем, у такого подхода есть свои обратные стороны: во-первых, он недостаточно интуитивен. Во-вторых, некоторые комбинации структур данных и алгоритмов могут оказаться недопустимыми или, что еще хуже, допустимыми, но бесполезными (например, обладающими недостаточным быстродействием). Таким образом, очень важно изучить основные возможности и потенциальные опасности STL, чтобы использовать все достоинства библиотеки и благополучно обойти ловушки. Примеры и дополнительная информация на эту тему неоднократно встречаются в оставшейся части этой главы.

Начнем; с простого примера демонстрирующего некоторые алгоритмы STL и принципы их использования:

#include "stdafx.h"

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> coll;

vector<int>::iterator pos;

// Вставка элементов от 1 до 6 в произвольном порядке

coll.push_back(2);

coll.push_back(5);

coll.push_back(4);

coll.push_back(1);

coll.push_back(6);

coll.push_back(3);

// Поиск и вывод минимального и максимального элементов

pos = min_element(coll.begin(), coll.end());

cout << "min: " << *pos << endl;

pos = max_element(coll.begin(), coll.end());

cout << "max: " << *pos << endl;

// Сортировка всех элементов

sort(coll.begin(),coll.end());

// Поиск первого элемента со значением, равным 3

pos = find(coll.begin(), coll.end(), // Интервал

3); //Значение

// Перестановка найденного элемента со значением 3

// и всех последующих элементов в обратном порядке.

reverse(pos, coll.end());

// Вывод всех элементов

for (pos = coll.begin(); pos != coll.end(); ++pos) {

cout << *pos << ' ';

}

cout << endl;

}

Чтобы использовать алгоритмы в программе, необходимо включить в нее заголовочный файл <algorithm>

Первые два алгоритма называются min_element( ) и max_element(). При вызове им передаются два параметра, определяющих интервал обрабатываемых элементов. Чтобы обработать все содержимое контейнера, просто используйте вызовы begln() и end(). Алгоритмы возвращают итераторы соответственно для минимального и максимального элементов. Таким образом, в показанной ниже команде алгоритм min_element() возвращает позицию минимального элемента (если таких элементов несколько, алгоритм возвращает позицию первого из них):

pos = min_element(coll.begin(), coll.end());

Следующая команда выводит найденный элемент:

cout << "min: " << *pos << endl;

Разумеется, поиск и вывод можно объединить в одну команду:

cout << *min_element(coll.begin(), coll.end(), end( )) << endl;

Следующим вызывается алгоритм sort(). Как нетрудно догадаться по названию, этот алгоритм сортирует элементы в интервале, определяемом двумя аргументами. Как обычно, вы можете задать собственный критерий сортировки. По умолчанию сортировка осуществляется с использованием оператора <. Таким образом, следующая команда сортирует все элементы контейнера по возрастанию:

sort (coll.begin( ), coll.end( ));

В конце концов элементы вектора будут расположены в следующем порядке:

1 2 3 4 5 6

Алгоритм find( ) ищет значение в заданном интервале. В нашем примере во всем контейнере ищется первый элемент со значением 3:

pos = find (colI.begin( ), coll.еnd ( ), // Интервал

3); //Значение

Если поиск оказался успешным, алгоритм find( ) возвращает итератор, установленный на первый найденный элемент. В случае неудачи возвращается итератор для позиции за концом интервала, определяемым вторым переданным аргументом. В нашем примере значение 3 находится в третьем элементе, поэтому pos ссылается на третий элемент coll.

Последним вызывается алгоритм reverse( ), который переставляет элементы переданного интервала в обратном порядке. В аргументах передается третий элемент, найденный алгоритмом find( ), и конечный итератор:

reverse (pos.coll.end( ));

В результате вызова переставляются элементы от третьего до последнего. Результат работы программы выглядит так:

min: 1

max: 6

1 2 6 5 4 3

Интервалы

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

Такой интерфейс чрезвычайно гибок, но потенциально опасен. Вызывающая сторона должна проследить за тем, чтобы первый и второй аргументы определяли действительный интервал, то есть итератор мог перейти от начала к концу интервала в процессе перебора элементов. А это означает, что оба итератора должны принадлежать одному контейнеру, а начало интервала не должно находиться после его конца. Если это условие не выполняется, возможны непредсказуемые последствия, включая зацикливание или нарушение защиты памяти. В этом отношении итераторы так же ненадежны, как обычные указатели. Однако из неопределенности поведения также следует, что реализации STL могут выявлять подобные ошибки и обрабатывать их по своему усмотрению.

Все алгоритмы работают с полуоткрытыми интервалами. Иначе говоря, интервал включает заданную начальную позицию, но конечная позиция в него не включается. В традиционной математической имеется два варианта обозначения полуоткрытых интервалов:

[начало, конец)

[начало, конец]

В книге используется первый вариант.

Концепция полуоткрытых интервалов не требует специальной обработки пустых коллекций. Тем не менее у нее также есть недостатки. Рассмотрим следующий пример:

#include "stdafx.h"

#include <iostream>

#include <list>

#include <algorithm>

using namespace std;

int main()

{

list<int> coll;

list<int>::iterator pos;

// Вставка элементов от 20 до 40

for (int i = 20; i<40; ++i) {

coll.push_back(i);

}

// Поиск позиции элемента со значением, равным 3

/*-такой элемент отсутствует, поэтому pos присваивается coll.end()

*/

pos = find(coll.begin(), coll.end(), // /Интервал

3); // Значение

/* Перестановка элементов от найденного до конца интервала. Поскольку итератор pos равен соll.end( ), то перестановка производится в пустом интервале.*/

reverse(pos, coll.end());

// Поиск позиций со значениями 25 и 25

list<int>::iterator pos25, pos35;

pos25 = find(coll.begin(), coll.end(), // Интервал

25); // Значение

pos35 = find(coll.begin(), coll.end(), // Интервал

35); // Значение

/* Вывод максимума по полученному интервалу

- обратите внимание: интервал содержит позицию роs25,

- но позиция pos35 в него не включается. */

cout << "max: " << *max_element(pos25, pos35) << endl;

// process the elements including the last position

cout << "max:" << *max_element(pos25, ++pos35) << endl;

}

В этом примере коллекция заполняется целыми числами от 20 до 40. После того как поиск элемента со значением 3 завершается неудачей, find() возвращает конец обработанного интервала - в данном случае coll.end() — и присваивает его переменной pos. Использование возвращаемого значения в качестве начала интервала при вызове reverse() не вызывает проблем, поскольку это приводит к следующему вызову:

reverse (coll.end( ), coll.end( ));

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

Но если алгоритм find( ) используется для определения первого и последнего элементов в подмножестве, следует помнить, что при определении интервала на основании полученных итераторов последний элемент исключается. Рассмотрим первый вызов max_element():

max_element (pos25, pos35)

При этом вызове будет найдено максимальное значение 34 вместо 35:

max: 34

Чтобы включить в интервал последний найденный элемент; необходимо перевести итератор на одну позицию вперед:

max_element (pos25, ++pos35)

На этот раз результат будет правильным:

max: 35

В этом примере контейнером является список, поэтому для перевода pos35 к следующей позиции был применен оператор ++. Если бы мы использовали итератор произвольного доступа (как в случае вектора или дека), задача также решалась бы с помощью выражения pos35 ++, поскольку итераторы произвольного доступа поддерживают математические операции.

Конечно, итераторы pos25 и pos35 можно использовать для поиска в подмножестве элементов. Чтобы поиск производился с включением позиции pos35, следует сместить позицию итератора. Пример:

// Увеличение pos35 для учета конца интервала при поиске

++pos35;

pos30 = find(pos25, роs35, // Интервал

30); //Значение

if(рos30 == pos35) { cout << "30 is NOT in the subrange" << endl;}

else { cout << "30 is in the subrange" << endl;}

Все примеры, приведенные в этом разделе, работают только потому, что нам точно известно, что позиция pos25 предшествует позиции pos35. В противном случае интервал [pos25, pos35] становится недействительным. Если вы не уверены в том, какой из элементов которому предшествует, то ситуация усложняется, а ошибка может привести к непредсказуемым последствиям.

Предположим, мы не знаем, что элемент со значением 25 предшествует элементу со значением 35. Более того, нельзя исключать, что одно или оба значения отсутствуют в контейнере. При использовании итератора произвольного доступа проверка выполняется оператором:

if(pos25 < pos35) {

// Действителен интервал [pos25, pos35)

}

else if(pos35 < pos25) { // Действителен интервал [pos35, pos25)

}

else {// Итераторы равны: следовательно, оба итератора находятся в позиции end()

}

Без итераторов произвольного доступа не существует простого и быстрого способа определить порядок следования итераторов. Единственное разумное решение — провести поиск одного итератора в интервале от начала до другого итератора или от другого итератора до конца. В этом случае алгоритм слегка изменяется: вместо того чтобы искать оба значения во всем исходном интервале, мы пытаемся определить, какое значение встречается первым. Пример:

pos25 = find(соll.begin(), coll.end(), // Интервал

25); // Значение

pos35 = find(coll.begin(), pos25, // Интервал

35); // Значение

if (pos35 != pos25) {

/* pos35 предшествует pos25; следовательно,

* действителен только интервал [pos35, pos25)

*/

…

}

else {

pos35 = find(pos25, coll.end(). // Интервал

35); // Значение

if (pos35 != pos25) {

/* pos25 предшествует pos35; следовательно,

* действителен только интервал [pos25, pos35)

*/

…

}

else {

// Итераторы равны: следовательно, оба итератора

// находятся в позиции end( )

…

}

В отличие от предыдущей версии поиск значения 35 производится не во всем множестве элементов coll. Сначала поиск ведется от начала до pos25. Если значение не найдено, поиск производится среди элементов, находящихся после pos25. В результате мы выясняем, какой итератор встречается раньше и какой интервал действителен.