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

Итераторы - это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы - это объекты, которые имеют operator*, возвращающий значение некоторого класса или встроенного типа T, называемого значимым типом (value type) итератора. Для каждого типа итератора X, для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния (distanсe type) итератора.

Так как итераторы - обобщение указателей, их семантика - обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них: ввода (input iterators), вывода (output iterators), последовательные (forward iterators), двунаправленные (bidirectional iterators) и произвольного доступа (random access iterators.) Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли быть иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые (mutable) или постоянные (constant) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.

Таблица 1. Отношения среди категорий итераторов

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными (past-the-end) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми (dereferenceable). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные (singular) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение - присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.

Итератор j называется доступным (reachable) из итератора i, если и только если имеется конечная последовательность применений operator++ к i, которая делает i==j. Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i, или i доступен из j, или оба доступны (i==j).

Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) - пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i, и до элемента, но не включая его, указываемого j. Диапазон [i,j) допустим, если и только если j доступен из i. Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.

Все категории итераторов требуют только те функции, которые осуществимы для данной категории со сложностью постоянного времени (амортизированные). Поэтому таблицы требований для итераторов не имеют столбца сложности.

В следующих разделах мы принимаем: a и b - значения X, n - значение типа расстояния Distance, u, tmp и m - идентификаторы, r и s - леводопустимые (lvalues) значения X, t - значение значимого типа T.

Итераторы ввода (Input iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора ввода для значимого типа T, если справедливы следующие выражения:

Таблица 2. Требования итератора ввода

ПРИМЕЧАНИЕ. Для итераторов ввода нет никаких требований на тип или значение r++ кроме требования, чтобы *r++ работал соответственным образом. В частности, r == s не подразумевает, что ++r == ++s. (Равенство не гарантирует свойство замены или ссылочной прозрачности.) Что касается ++r, то нет больше никаких требований на значения любых копий r за исключением того, что они могут быть безопасно уничтожены или присвоены. После выполнения ++r не требуется, чтобы были копии (предыдущего) r в области ==. Алгоритмы с итераторами ввода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными (single pass) алгоритмами. Не требуется, чтобы значимый тип T был леводопустимым типом (lvalue type). Эти алгоритмы могут использоваться с входными потоками как источниками входных данных через класс istream_iterator.

Итераторы вывода (Output iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора вывода, если справедливы следующие выражения:

Таблица 3. Требования итератора вывода

ПРИМЕЧАНИЕ. Единственное допустимое использование operator* - на левой стороне выражения присваивания. Присваивание через то же самое значение итератора происходит только однажды. Алгоритмы с итераторами вывода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными (single pass) алгоритмами. Равенство и неравенство не обязательно определены. Алгоритмы, которые берут итераторы вывода, могут использоваться с выходными потоками для помещения в них данных через класс ostream_iterator, также как с итераторами вставки и вставляющими указателями. В частности, следующие два условия должны соблюдаться: во-первых, через любое значение итератора должно выполняться присваивание до его увеличения (то есть, для итератора вывода i недопустима последовательность кода i++; i++;); во-вторых, любое значение итератора вывода может иметь только одну активную копию в любое данное время (например, недопустима последовательность кода i = j; *++i = a; *j = b;).

Последовательные итераторы (Forward iterators)

Класс или встроенный тип X удовлетворяет требованиям последовательного итератора, если справедливы следующие выражения:

Таблица 4. Требования последовательного итератора

ПРИМЕЧАНИЕ. Тот факт, что r == s подразумевает ++r == ++s (что неверно для итераторов ввода и вывода) и что удалено ограничение на число присваиваний через итератор (которое применяется к итераторам вывода), позволяет использование многопроходных однонаправленных алгоритмов с последовательными итераторами.

Двунаправленные итераторы (Bidirectional iterators)

Класс или встроенный тип X удовлетворяет требованиям двунаправленного итератора, если к таблице, которая определяет последовательные итераторы, мы добавим следующие строки:

Таблица 5. Требования двунаправленного итератора (в дополнение к последовательному итератору)

ПРИМЕЧАНИЕ. Двунаправленные итераторы позволяют алгоритмам перемещать итераторы назад так же, как вперёд.

Итераторы произвольного доступа (Random access iterators)

Класс или встроенный тип X удовлетворяет требованиям итераторов произвольного доступа, если к таблице, которая определяет двунаправленные итераторы, мы добавим следующие строки:

Таблица 6: Требования итератора произвольного доступа (в дополнение к двунаправленному итератору)

Теги итераторов (Iterator tags)

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);}

template ‹class BidirectionalIterator›

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

 _reverse(first, last, value_type(first), distance_type(first));

}

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;

 }

}

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);

}

template ‹class T›

inline random_access_iterator_tag iterator_category(const T*) {

 return random_access_iterator_tag();

}

template ‹class T›

inline bidirectional_iterator_tag iterator_category(const BinaryTreeIterator‹T›&) {

 return bidirectional_iterator_tag();

}

template ‹class BidirectionalIterator›

inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {

 evolve(first, last, iterator_category(first));

}

template ‹class BidirectionalIterator›

void evolve(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) {

 //… более универсальный, но менее эффективный алгоритм

}

template ‹class RandomAccessIterator›

void evolve(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {

 //… более эффективный, но менее универсальный алгоритм

}

// iterator tags (теги итераторов)

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag {};

struct bidirectional_iterator_tag {};

struct random_access_iterator_tag {};

// iterator bases (базовые классы итераторов)

template ‹class T, class Distance = ptrdiff_t› struct input_iterator {};

struct output_iterator {};

// output_iterator не шаблон, потому что у итераторов вывода

// не определены ни значимый тип, ни тип расстояния.

template ‹class T, class Distance = ptrdiff_t›

struct forward_iterator {};

template ‹class T, class Distance = ptrdiff_t›

struct bidirectional_iterator {};

template ‹class T, class Distance = ptrdiff_t›

struct random_access_iterator {};

// iterator_category (функции категорий итераторов)

template ‹class T, class Distance›

inline input_iterator_tag iterator_category(const input_iterator‹T, Distance›&) {

 return input_iterator_tag();

}

inline output_iterator_tag iterator_category(const output_iterator&) {

 return output_iterator_tag();

}

template ‹class T, class Distance›

inline forward_iterator_tag iterator_category(const forward_iterator‹T, Distance›&) {

 return forward_iterator_tag();

}

template ‹class T, class Distance› 

inline bidirectional_iterator_tag iterator_category(const bidirectional_iterator‹T, Distance›&) {

 return bidirectional_iterator_tag();

}

template ‹class T, class Distance›

inline random_access_iterator_tag iterator_category(const random_access_iterator‹T, Distance›&) {

 return random_access_iterator_tag();

}

template ‹class T›

inline random_access_iterator_tag iterator_category(const T*) {

 return random_access_iterator_tag();

}

// value_type of iterator (функции значимого типа итераторов)

template ‹class T, class Distance›

inline T* value_type(const input_iterator‹T, Distance›&) {

 return (T*) (0);

}

template ‹class T, class Distance›

inline T* value_type(const forward_iterator‹T, Distance›&) {

 return (T*) (0);

}

template ‹class T, class Distance›

inline T* value_type(const bidirectional_iterator‹T, Distance›&) {

 return (T*) (0);

}

template ‹class T, class Distance›

inline T* value_type(const random_access_iterator‹T, Distance›&) {

 return (T*) (0);

}

template ‹class T›

inline T* value_type(const T*) {return (T*) (0);}

// distance_type of iterator (функции типа расстояния итераторов)

template ‹class T, class Distance›

inline Distance* distance_type(const input_iterator‹T, Distance›&) {

 return (Distance*) (0);

}

template ‹class T, class Distance›

inline Distance* distance_type(const forward_iterator‹T, Distance›&) {

 return (Distance*) (0);

}

template ‹class T, class Distance›

inline Distance* distance_type(const bidirectional_iterator‹T, Distance›&) {

 return (Distance*) (0);

}

template ‹class T, class Distance›

inline Distance* distance_type(const random_access_iterator‹T, Distance›&) {

 return (Distance*) (0);

}

template ‹class T›

inline ptrdiff_t* distance_type(const T*) {return (ptrdiff_t*) (0);}

class MyIterator: public bidirectional_iterator ‹double, long› {

 // код, осуществляющий ++, и т.д.

};

Операции с итераторами (Iterator operations)

Так как только итераторы произвольного доступа обеспечивают + и - операторы, библиотека предоставляет две шаблонные функции advance и distance. Эти функции используют + и - для итераторов произвольного доступа (и имеют, поэтому, сложность постоянного времени для них); для итераторов ввода, последовательных и двунаправленных итераторов функции используют ++, чтобы обеспечить реализацию со сложностью линейного времени. advance берет отрицательный параметр n только для итераторов произвольного доступа и двунаправленных итераторов. advance увеличивает (или уменьшает для отрицательного n) итераторную ссылку i на n. distance увеличивает n на число единиц, сколько требуется, чтобы дойти от first до last.

template ‹class InputIterator, class Distance›

inline void advance(InputIterator& i, Distance n);

template ‹class InputIterator, class Distance›

inline void distance(InputIterator first, InputIterator last, Distance& n);

distance должна быть функцией 3-х параметров, сохраняющей результат в ссылке вместо возвращения результата, потому что тип расстояния не может быть выведен из встроенных итераторных типов, таких как int*.