Глава 13. Итераторы и функциональные объекты

329

дующему элементу — с помощью операции инкремента ++. Для всех итераторов определены также присваивание, проверка на равенство и неравенство.

Данные могут быть организованы различным образом — например, в виде массива, списка, вектора или дерева. Для каждого вида последовательности требуется свой тип итератора, поддерживающий различные наборы операций. В соответствии с набором обеспечиваемых операций итераторы делятся на пять категорий, описанных в табл. 13.1. Приведенные в таблице операции обеспечиваются за постоянное время.

Пусть i и j — итераторы одного вида, х — переменная того же типа, что и элемент последовательности, п — целая величина. Тогда допустимы выражения:

Категория итератора	Операции	Контейнеры
входной (input)	х = *i	все
выходной (output)	*i = х	все
прямой (forward)	х = *i, *i = x	все
двунаправленный (bidirectional)	x = *i, *i = x, --i, i--	все
произвольного доступа (random access)	x = *i, *i = x, --i, i-- i + n, i - n, i += n, i -= n i < j, i > j, i <- j, i ^>e j	все, кроме list

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

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

Итераторные классы и функции описаны в заголовочном файле <iterator>. При использовании стандартных контейнеров этот файл подключается автоматически.

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

330

Часть III. Стандартная библиотека

Итератор может быть действительным (когда он указывает на какой-либо элемент) или недействительным. Итератор может стать недействительным в следующих случаях:

• итератор не был инициализирован;

• контейнер, с которым он связан, изменил размеры или уничтожен;

• итератор указывает на конец последовательности.

Конец последовательности представляется как указатель на элемент, следующий за последним элементом последовательности. Этот указатель всегда существует. Такой подход позволяет не рассматривать пустую последовательность как особый случай. Понятия «нулевой итератор» не существует.

Поскольку итераторы используются для работы с объектами, на которые они указывают (например, для получения значения элемента контейнера), требуется определить соответствующие типы. Для этого в заголовочном файле <iterator> определен шаблон iterator_traits (trait в переводе с английского — характерная черта).

tempiate<class Iter> struct iterator_traits{

typedef typename Iter::difference_type difference_type;

typedef typename Iter::value_type value_type;

typedef typename Iter::pointer pointer;

typedef typename Iter::reference reference;

typedef typename Iter::iterator_category iterator_category;

}: Ключевое слово typename необходимо для того, чтобы компилятор мог опознать Iter как имя типа. iterator_category — это тип итератора, который определяет, какие он поддерживает операции. Тип di f ference_type служит для выражения разности между двумя итераторами.

В заголовочном файле описаны следующие типы итераторов:

struct input_iterator_tag{};

struct output_iterator_tag{};

struct forward_iterator_tag: public input_iterator_tag{};

struct bidirectional_iterator_tag:

public forward_iterator_tag{}; struct random_access_iterator_tag:

public bidirectional_iterator_tag{};

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

Для обычных указателей в целях повышения эффективности определены специализации шаблона iterator_traits (о специализациях шаблонов рассказывалось на с. 220):

tempiate<class T> struct iterator_traits<T*>{ typedef ptrdiff_t difference_type;