Более мощная категория итераторов состоит из однонаправленных итераторов (forward iterators). Такие итераторы могут делать все, что делают итераторы ввода и вывода, плюс разрешают читать и писать в то место, на которое указывают, более одного раза. Это делает их удобными для многопроходных алгоритмов. STL не предоставляет реализацию однонаправленных связных списков, но в некоторых библиотеках они есть (и обычно называются slist); итераторы таких контейнеров являются однонаправленными. Итераторы кэшированных контейнеров в библиотеке TR1 (см. правило 54) также могут быть однонаправленными.
Двунаправленные итераторы (bidirectional iterators) добавляют к функциональности однонаправленных итераторов возможность перемещения назад. Итераторы для STL-контейнера list относятся к этой категории, равно как и итераторы для set, multiset, map и multimap.
Наиболее мощная категория итераторов – это итераторы с произвольным доступом (random access iterators). Итераторы этого типа добавляют к функциям двунаправленных итераторов «итераторную арифметику», то есть возможность перемещения вперед и назад на заданное расстояние, затрачивая на это постоянное время. Такая арифметика аналогична арифметике указателей, что неудивительно, поскольку итераторы с произвольным доступом моделируют встроенные указатели, а встроенные указатели могут вести себя как итераторы с произвольным доступом. Итераторы для vector, deque и string являются итераторами с произвольным доступом.
Для каждой из пяти категорий итераторов C++ в стандартной библиотеке имеется соответствующая «структура-тэг» (tag struct):
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_teg: public bidirectional_iterator_tag {};
Отношения наследования между этими структурами корректно выражают взаимосвязь типа «является» (см. правило 32): верно, что все однонаправленные итераторы являются также итераторами ввода и т. д. Вскоре мы увидим примеры использования такого наследования.
Но вернемся к операции advance. Поскольку у разных итераторов возможности различны, то можно было при реализации advance воспользоваться «наименьшим общим знаменателем», то есть организовать цикл, в котором итератор увеличивается или уменьшается на единицу. Но такой подход требует линейных затрат времени. Итераторы с произвольным доступом обеспечивают доступ к любому элементу контейнера за постоянное время, и, конечно, мы бы хотели воспользоваться этим преимуществом, коль скоро оно имеется.
В действительности хотелось бы реализовать advance как-то так:
template
void advance(IterT& iter, DistT d)
{
if (iter является итератором с произвольным доступом) {
iter += d; // использовать итераторную арифметику
} // для итераторов с произвольным доступом
else {
if(d>=0) {while (d–) ++iter;} // вызывать ++ или – в цикле
else {while(d++) –iter;} // для итераторов других категорий
}
}
Но для этого нужно уметь определять, является ли iter итератором с произвольным доступом, что, в свою очередь, требует знания о том, что его тип – IterT – относится к категории итераторов с произвольным доступом. Другими словами, нам нужно получить некоторую информацию о типе. Именно для этого и служат характеристики (traits): получить информацию о типе во время компиляции.
Traits – это не ключевое слово и не предопределенная конструкция в C++; это техника и соглашение, которому следуют программисты. Одним из требований, предъявляемых к ней, является то, что она должна одинаково хорошо работать и для встроенных типов, и для типов, определяемых пользователем. Например, при вызове для обычного указателя (типа const char*) или значения типа int операция advance должна работать, а это значит, что техника характеристик должна быть применима и к встроенным типам.
Тот факт, что характеристики должны работать со встроенными типами, означает, что нельзя рассчитывать на размещение специальной информации внутри типа, потому что в указателях никакую информацию не разместишь. Поэтому характеристическая информация о типе должна быть внешней по отношению к типу. Стандартная техника заключается в помещении ее в шаблон, для которого существует одна или несколько специализаций. Для итераторов в стандартной библиотеке существует шаблон iterator_traits:
template // шаблон для информации
struct iterator_traits; // о типах итераторов
Как видите, iterator_traits – это структура. По соглашению характеристики всегда реализуются в виде структур. Другое соглашение заключается в том, что структуры, используемые для их реализации, почему-то называются классами- характеристиками.
Смысл iterator_traits состоит в том, что для каждого типа IterT определяется псевдоним typedef iterator_category для структуры iterator_traits. Этот typedef идентифицирует категорию, к которой относится итератор IterT.
Реализация этой идеи в iterator_traits состоит из двух частей. Первая – вводится требование, чтобы все определяемые пользователем типы итераторов имели внутри себя вложенный typedef с именем iterator_category, который задает соответствующую структуру-тэг. Например, итераторы deque являются итераторами с произвольным доступом, поэтому класс итераторов deque должен выглядеть примерно так:
template <…>
class deque {
public:
class iterator {
public:
typedef random_access_iterator_tag iterator_category;
...
};
...
};
Итераторы для контейнеров list являются двунаправленными, поэтому для них объявление выглядит так:
template <…>
class list {
public:
class iterator {
public:
typedef bidirectional_iterator_tag iterator_category;
};
...
};
В шаблоне iterator_traits просто повторен находящийся внутри класса итератора typedef:
// iterator_category для типа IterT – это то, что сообщает о нем сам IterT
// см. в правиле 42 информацию об использовании “typedef typename”
template
struct iterator_traits {
typedef typename IterT::iterator_category iterator_category;
...
};
Это работает с пользовательскими типами, но не подходит для итераторов, которые являются указателями, потому что не существует указателей с вложенными typedef. Поэтому во второй части шаблона iterator_traits реализована поддержка итераторов, являющихся указателями.
С этой целью iterator_traits представляет частичную специализацию шаблонов для типов указателей. Указатели ведут себя как итераторы с произвольным доступом, поэтому в iterator_traits для них указана именно эта категория:
template // частичная специализация шаблона
struct iterator_traits // для встроенных типов указателей
{
typedef random_access_iterator_tar iterator_category;
...
};
Теперь вы должны понимать, как проектируется и реализуется класс-характеристика:
• Идентифицировать информацию о типе, которую вы хотели бы сделать доступной (например, для итераторов – это их категория).
• Выбрать имя для обозначения этой информации (например, iterator_category).
• Предоставить шаблон и набор его специализаций (например, iterator_traits), которые содержат информацию о типах, которые вы хотите поддерживать.
Имея шаблон iterator_traits, – на самом деле std::iterator_traits, потому что он является частью стандартной библиотеки C++, – мы можем уточнить наш псевдокод для advance:
template
void advance(IterT& iter, DistT d)
{
if (typeid(typename std::iterator_traits::iterator_category)==
typeid(std::random_access_iterator_tag))
...
}
Выглядит многообещающе, но это не совсем то, что нужно. Во-первых, возникнет проблема при компиляции, но ее мы рассмотрим в правиле 48; а пока остановимся на более фундаментальном обстоятельстве. Тип IterT известен на этапе компиляции, поэтому iterator_traits