РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Таблица 1. Отношения среди категорий итераторов

Произвольного доступа -› Двунаправленные -› Последовательные -->	- › Ввода
	- › Вывода

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными (past-the-end) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми (dereferenceable). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные (singular) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение - присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.

Итератор j называется доступным (reachable) из итератора i, если и только если имеется конечная последовательность применений operator++ к i, которая делает i==j. Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i, или i доступен из j, или оба доступны (i==j).

Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) - пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i, и до элемента, но не включая его, указываемого j. Диапазон [i,j) допустим, если и только если j доступен из i. Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.

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

В следующих разделах мы принимаем: a и b - значения X, n - значение типа расстояния Distance, u, tmp и m - идентификаторы, r и s - леводопустимые (lvalues) значения X, t - значение значимого типа T.

Итераторы ввода (Input iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора ввода для значимого типа T, если справедливы следующие выражения:

Таблица 2. Требования итератора ввода

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
X(a)	-	-	X(a) - копия a. примечание: предполагается деструктор.
X u(a); X u = a;	-	-	после: u - копия a.
u = a	X&	-	после: u - копия a.
a == b	обратимый в bool	-	если a - копия b, тогда a == b возвращает true. == - это отношение эквивалентности в области действия ==.
a!= b	обратимый в bool	!(a == b)	-
*a	обратимый в T	-	до: a - разыменовываемое. если a - копия b, то *a эквивалентно *b.
++r	X&	-	до: r - разыменовываемое. после: r - разыменовываемое или r - законечное.
void r++	void	void ++r	-
*r++	Т	{X tmp = r; ++r; return tmp;}	-

ПРИМЕЧАНИЕ. Для итераторов ввода нет никаких требований на тип или значение r++ кроме требования, чтобы *r++ работал соответственным образом. В частности, r == s не подразумевает, что ++r == ++s. (Равенство не гарантирует свойство замены или ссылочной прозрачности.) Что касается ++r, то нет больше никаких требований на значения любых копий r за исключением того, что они могут быть безопасно уничтожены или присвоены. После выполнения ++r не требуется, чтобы были копии (предыдущего) r в области ==. Алгоритмы с итераторами ввода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными (single pass) алгоритмами. Не требуется, чтобы значимый тип T был леводопустимым типом (lvalue type). Эти алгоритмы могут использоваться с входными потоками как источниками входных данных через класс istream_iterator.

Итераторы вывода (Output iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора вывода, если справедливы следующие выражения:

Таблица 3. Требования итератора вывода

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
X(a)	-	-	*a = t эквивалентно *X(a) = t. примечание: предполагается деструктор.
X u(a); X u = a;	-	-	-
*a = t	результат не используется	-	-
++r	X&	-	-
r++	Х или Х&	-	-

ПРИМЕЧАНИЕ. Единственное допустимое использование operator* - на левой стороне выражения присваивания. Присваивание через то же самое значение итератора происходит только однажды. Алгоритмы с итераторами вывода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными (single pass) алгоритмами. Равенство и неравенство не обязательно определены. Алгоритмы, которые берут итераторы вывода, могут использоваться с выходными потоками для помещения в них данных через класс ostream_iterator, также как с итераторами вставки и вставляющими указателями. В частности, следующие два условия должны соблюдаться: во-первых, через любое значение итератора должно выполняться присваивание до его увеличения (то есть, для итератора вывода i недопустима последовательность кода i++; i++;); во-вторых, любое значение итератора вывода может иметь только одну активную копию в любое данное время (например, недопустима последовательность кода i = j; *++i = a; *j = b;).

Последовательные итераторы (Forward iterators)

Класс или встроенный тип X удовлетворяет требованиям последовательного итератора, если справедливы следующие выражения:

Таблица 4. Требования последовательного итератора 

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
X u;	-	-	примечание: u может иметь исключительное значение. примечание: предполагается деструктор.
X()	-	-	примечание: X() может быть исключительным.
X(a);	-	-	a == X(a)
X u(a); X u = a;	-	X u; u = a;	после: u == a.
a == b	обратимый в bool	-	== - это отношение эквивалентности.
a!= b	обратимый в bool	!(a == b)	-
r = a	X&	-	после: r == a.
*a	обратимый в T	-	до: a - разыменовываемое. a==b подразумевает *a==*b. Если X - модифицируемый, то *a = t - допустимо.
++r	X&	-	до: r - разыменовываемое. после: r - разыменовываемое или r - законечное. r == s и r - разыменовываемое подразумевает ++r==++s. &r==&++r.
r++	X	{X tmp = r; ++ r; return tmp;}	-

ПРИМЕЧАНИЕ. Тот факт, что r == s подразумевает ++r == ++s (что неверно для итераторов ввода и вывода) и что удалено ограничение на число присваиваний через итератор (которое применяется к итераторам вывода), позволяет использование многопроходных однонаправленных алгоритмов с последовательными итераторами.

Двунаправленные итераторы (Bidirectional iterators)

Класс или встроенный тип X удовлетворяет требованиям двунаправленного итератора, если к таблице, которая определяет последовательные итераторы, мы добавим следующие строки:

Таблица 5. Требования двунаправленного итератора (в дополнение к последовательному итератору)

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
--r	X&	-	до: существует s такое, что r==++s. после: s - разыменовываемое. --(++r)==r. --r==--s подразумевает r==s.&r==&--r.
r--	X	{X tmp = r; --r; return tmp;}	-

ПРИМЕЧАНИЕ. Двунаправленные итераторы позволяют алгоритмам перемещать итераторы назад так же, как вперёд.

Итераторы произвольного доступа (Random access iterators)

Класс или встроенный тип X удовлетворяет требованиям итераторов произвольного доступа, если к таблице, которая определяет двунаправленные итераторы, мы добавим следующие строки:

Таблица 6: Требования итератора произвольного доступа (в дополнение к двунаправленному итератору)

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
r += n	X&	{Distance m = n; if(m ›= 0) while(m--) ++r; else while(m++) --r; return r;}	-
a + n n + a	X	{X tmp = a; return tmp += n;}	a + n == n + a.
r -= n	X&	return r += -n;	-
a - n	X	{X tmp = a; return tmp -= n;}	-
b - a	Distance	-	до: существует значение n типа Distance такое, что a+n=b. b==a+(b-a).
a[n]	обратимый в T	*(a + n)	-
a ‹ b	обратимый в bool	b - a › 0	‹ - это отношение полного упорядочения
a › b	обратимый в bool	b ‹ a	› - это отношение полного упорядочения, противоположное ‹.
a ›= b	обратимый в bool	!(a ‹ b)	-
a ‹= b	обратимый в bool	!(a › b)	-

Теги итераторов (Iterator tags)

Чтобы осуществлять алгоритмы только в терминах итераторов, часто бывает необходимо вывести тип значения и тип расстояния из итератора. Для решения этой задачи требуется, чтобы для итератора i любой категории, отличной от итератора вывода, выражение value_type(i) возвращало (T*)(0), а выражение distance_type(i) возвращало (Distance*)(0). Для итераторов вывода эти выражения не требуются.

Примеры использования тегов итераторов

Для всех типов обычных указателей мы можем определить value_type и distance_type с помощью следующего:

template ‹class T›

inline T* value_type(const T*) {return (T*)(0);}

template ‹class T›

inline ptrdiff_t* distance_type(const T*) {return (ptrdiff_t*)(0);}

Тогда, если мы хотим осуществить обобщённую функцию reverse, мы пишем следующее:

template ‹class BidirectionalIterator›

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

 _reverse(first, last, value_type(first), distance_type(first));

}

где _reverse определена следующим образом:

template ‹class BidirectionalIterator, class T, class Distance›

void _reverse(BidirectionalIterator first, BidirectionalIterator last, T*, Distance*) {

 Distance n;

 distance(first, last, n); // смотри раздел "Операции с итераторами"

 --n;

 while (n › 0) {

  T tmp = *first;

  *first++ = *--last;

  *last = tmp;

  n -= 2;

 }

}

Если имеется дополнительный тип указателя _huge такой, что разность двух указателей _huge имеет тип long long, мы определяем:

template ‹class T›

inline T* value_type(const T _huge *) {return (T*) (0);}

template ‹class T›

inline long long* distance_type(const T _huge *) {

 return (long long*)(0);

}

Часто желательно для шаблонной функции выяснить, какова наиболее специфичная категория её итераторного аргумента, так чтобы функция могла выбирать наиболее эффективный алгоритм во время компиляции. Чтобы облегчить это, библиотека вводит классы тегов категорий (category tag), которые используются как теги времени компиляции для выбора алгоритма. Это следущие теги: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag и random_access_iterator_tag. Каждый итератор i должен иметь выражение iterator_category(i), определённое для него, которое возвращает тег наиболее специфичной категории, который описывает его поведение. Например, мы определяем, что все типы указателей находятся в категории итераторов произвольного доступа:

template ‹class T›

inline random_access_iterator_tag iterator_category(const T*) {

 return random_access_iterator_tag();

}

Определяемый пользователем итератор BinaryTreeIterator может быть включен в категорию двунаправленных итераторов следующим образом:

template ‹class T›

inline bidirectional_iterator_tag iterator_category(const BinaryTreeIterator‹T›&) {

 return bidirectional_iterator_tag();

}

Если шаблонная функция evolve хорошо определена для двунаправленных итераторов, но может быть осуществлена более эффективно для итераторов произвольного доступа, тогда реализация выглядит так:

template ‹class BidirectionalIterator›

inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {

 evolve(first, last, iterator_category(first));

}

template ‹class BidirectionalIterator›

void evolve(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) {

 //… более универсальный, но менее эффективный алгоритм

}

template ‹class RandomAccessIterator›

void evolve(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {

 //… более эффективный, но менее универсальный алгоритм

}

Примитивы, определённые в библиотеке

Чтобы упростить задачу определения iterator_category, value_type и distance_type для определяемых пользователем итераторов, библиотека обеспечивает следующие предопределённые классы и функции:

// iterator tags (теги итераторов)

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag {};

struct bidirectional_iterator_tag {};

struct random_access_iterator_tag {};