Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

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

template ‹class T›

inline random_access_iterator_tag iterator_category(const T*) {

 return random_access_iterator_tag();

}

Определяемый пользователем итератор BinaryTreeIterator может быть включен в категорию двунаправленных итераторов следующим образом:

template ‹class T›

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

 return bidirectional_iterator_tag();

}

Если шаблонная функция evolve хорошо определена для двунаправленных итераторов, но может быть осуществлена более эффективно для итераторов произвольного доступа, тогда реализация выглядит так:

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_category, value_type и distance_type для определяемых пользователем итераторов, библиотека обеспечивает следующие предопределённые классы и функции:

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

Если пользователь хочет определить двунаправленный итератор для некоторой структуры данных, содержащей 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.

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*.

Функциональные объекты

Функциональные объекты - это объекты, для которых определён operator(). Они важны для эффективного использования библиотеки. В местах, где ожидается передача указателя на функцию алгоритмическому шаблону, интерфейс установлен на приём объекта с определённым operator(). Это не только заставляет алгоритмические шаблоны работать с указателями на функции, но также позволяет им работать с произвольными функциональными объектами. Использование функциональных объектов вместе с функциональными шаблонами увеличивает выразительную мощность библиотеки также, как делает результирующий код более эффективным. Например, если мы хотим поэлементно сложить два вектора a и b, содержащие double, и поместить результат в a, мы можем сделать зто так: