Чтение онлайн

на главную - закладки

Жанры

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

Менг Ли

Шрифт:
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после
r += n X& {Distance m = n; if(m ›= 0) while(m--) ++r; else while(m++) --r; return r;}
a + n n + a X {X tmp = a; return tmp += n;} a + n == n + a.
r -= n X& return r += -n;
a - n X {X tmp = a; return tmp -= n;}
b - a Distance до:
существует значение n типа Distance такое, что a+n=b. b==a+(b-a).
a[n] обратимый в T *(a + n) –  
a ‹ b обратимый в bool b - a › 0 ‹ - это отношение полного упорядочения
a › b обратимый в bool b ‹ a › - это отношение полного упорядочения, противоположное ‹.
a ›= b обратимый в bool !(a ‹ b) –  
a ‹= b обратимый в bool !(a › b)

Теги итераторов (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 {};

Поделиться:
Популярные книги

На границе империй. Том 8

INDIGO
12. Фортуна дама переменчивая
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 8

Покоривший СТЕНУ 6: Пламя внутри

Мантикор Артемис
6. Покоривший СТЕНУ
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Покоривший СТЕНУ 6: Пламя внутри

Идеальный мир для Демонолога 8

Сапфир Олег
8. Демонолог
Фантастика:
боевая фантастика
юмористическая фантастика
аниме
5.00
рейтинг книги
Идеальный мир для Демонолога 8

Эфемер

Прокофьев Роман Юрьевич
7. Стеллар
Фантастика:
боевая фантастика
рпг
7.23
рейтинг книги
Эфемер

Блуждающие огни

Панченко Андрей Алексеевич
1. Блуждающие огни
Фантастика:
боевая фантастика
космическая фантастика
попаданцы
5.00
рейтинг книги
Блуждающие огни

Экспансия: Катаклизм. Том 3

Дорничев Дмитрий
3. Планетарный десант
Фантастика:
боевая фантастика
космическая фантастика
5.00
рейтинг книги
Экспансия: Катаклизм. Том 3

Проводник

Кораблев Родион
2. Другая сторона
Фантастика:
боевая фантастика
рпг
7.41
рейтинг книги
Проводник

Мастер 6

Чащин Валерий
6. Мастер
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Мастер 6

Бастард Императора. Том 13

Орлов Андрей Юрьевич
13. Бастард Императора
Фантастика:
попаданцы
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Бастард Императора. Том 13

Прометей: каменный век II

Рави Ивар
2. Прометей
Фантастика:
альтернативная история
7.40
рейтинг книги
Прометей: каменный век II

Вернуть Боярство

Мамаев Максим
1. Пепел
Фантастика:
фэнтези
попаданцы
5.40
рейтинг книги
Вернуть Боярство

Династия. Феникс

Майерс Александр
5. Династия
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Династия. Феникс

Девяностые приближаются

Иванов Дмитрий
3. Девяностые
Фантастика:
попаданцы
альтернативная история
7.33
рейтинг книги
Девяностые приближаются

Призыватель нулевого ранга

Дубов Дмитрий
1. Эпоха Гардара
Фантастика:
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Призыватель нулевого ранга