Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
ПРИМЕЧАНИЕ. Для итераторов ввода нет никаких требований на тип или значение 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)
