ПРИМЕЧАНИЕ. Тот факт, что 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), определённое для него, которое возвращает тег наиболее специфичной категории, который описывает его поведение. Например, мы определяем, что все типы указателей находятся в категории итераторов произвольного доступа: