Руководство по стандартной библиотеке шаблонов (STL)

Класс или встроенный тип 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)