РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Менг Ли

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

Если пользователь хочет определить двунаправленный итератор для некоторой структуры данных, содержащей double, и такой, чтобы работал с большой (large) моделью памяти компьютера, то это может быть сделано таким определением:

class MyIterator: public bidirectional_iterator ‹double, long› {

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

};

Тогда нет необходимости определять iterator_category, value_type, и distance_type в MyIterator.

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

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