Эффективное использование C++. 55 верных способов улучшить структуру и код ваших программ

// если d < 0, то перемещает iter
// назад

Концептуально advance делает то же самое, что предложение iter+=d, но таким способом advance не может быть реализован, потому что только итераторы с произвольным доступом поддерживают операцию +=. Для менее мощных итераторов advance реализуется путем повторения операции ++ или – ровно d раз.

А вы не помните, какие есть категории итераторов в STL? Не страшно, дадим краткий обзор. Существует пять категорий итераторов, соответствующих операциям, которые они поддерживают. Итераторы ввода ( input iterators) могут перемещаться только вперед, по одному шагу за раз, и позволяют читать только то, на что они указывают в данный момент, причем прочитать значение можно лишь один раз. Они моделируют указатель чтения из входного файла. К этой категории относится библиотечный итератор C++ iostream_iterator. Итераторы вывода (output iterators) устроены аналогично, но служат для вывода: перемещаются только вперед, по одному шагу за раз, позволяют записывать лишь в то место, на которое указывают, причем записать можно только один раз. Они моделируют указатель записи в выходной файл. К этой категории относится итератор ostream_iterator. Это самые «слабые» категории итераторов. Поскольку итераторы ввода и вывода могут перемещаться только в прямом направлении и позволяют лишь читать или писать туда, куда указывают, причем лишь единожды, они подходят только для однопроходных алгоритмов.

Более мощная категория итераторов состоит из однонаправленных итераторов (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<typename IterT, typename DistT>
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<typename IterT> // шаблон для информации
struct iterator_traits; // о типах итераторов

Как видите, iterator_traits – это структура. По соглашению характеристики всегда реализуются в виде структур. Другое соглашение заключается в том, что структуры, используемые для их реализации, почему-то называются классами- характеристиками.

Смысл iterator_traits состоит в том, что для каждого типа IterT определяется псевдоним typedef iterator_category для структуры iterator_traits<IterT>. Этот typedef идентифицирует категорию, к которой относится итератор IterT.

Реализация этой идеи в iterator_traits состоит из двух частей. Первая – вводится требование, чтобы все определяемые пользователем типы итераторов имели внутри себя вложенный typedef с именем iterator_category, который задает соответствующую структуру-тэг. Например, итераторы deque являются итераторами с произвольным доступом, поэтому класс итераторов deque должен выглядеть примерно так:

template <…>
class deque {
public:
class iterator {
public:
typedef random_access_iterator_tag iterator_category;
...
};