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

 //… более универсальный, но менее эффективный алгоритм
}
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);