Эффективное использование C++. 55 верных способов улучшить структуру и код ваших программ

Майерс Скотт

template <typename T> // определение шаблона

const Rational<T> doMultiply( const Rational<T>& lhs, // вспомогательной

const Rational<T>& rhs) // функции

{ // в заголовочном файле

return Rational(lhs.numerator * rhs.numerator, // при необходимости

lhs.denominator * rhs.denominator);

}

Конечно, будучи шаблоном, doMultiply не поддерживает умножения значений разного типа, но ей это и

не нужно. Она вызывается только из operator*, который обеспечивает поддержку параметров смешанного типа! По существу, функция operator* поддерживает любые преобразования типа, необходимые для перемножения объектов класса Rational, а затем передает эти два объекта соответствующей конкретизации шаблона doMultiply, которая и выполняет собственно операцию умножения. Кооперация в действии, не так ли?

Что следует помнить

• Когда вы пишете шаблон класса, в котором есть функции, нуждающиеся в неявных преобразованиях типа для всех параметров, определяйте такие функции как друзей внутри шаблона класса.

Правило 47: Используйте классы-характеристики для предоставления информации о типах

В основном библиотека STL содержит шаблоны контейнеров, итераторов и алгоритмов, но есть в ней и некоторые служебные шаблоны. Один из них называется advance. Шаблон advance перемещает указанный итератор на заданное расстояние:

template <typename T, typename DistT> // перемещает итератор iter

void advance(Iter T& iter, DistT d); // на d элементов вперед

// если d < 0, то перемещает iter

// назад

Концептуально advance делает то же самое, что предложение iter+=d, но таким способом advance не может быть реализован, потому что только итераторы с произвольным доступом поддерживают операцию +=. Для менее мощных итераторов advance реализуется путем повторения операции ++ или – ровно d раз.

А вы не помните, какие есть категории итераторов в STL? Не страшно, дадим краткий обзор. Существует пять категорий итераторов, соответствующих операциям, которые они поддерживают. Итераторы ввода ( input iterators) могут перемещаться только вперед, по одному шагу за раз, и позволяют читать только то, на что они указывают в данный момент, причем прочитать значение можно лишь один раз. Они моделируют указатель чтения из входного файла. К этой категории относится библиотечный итератор C++ iostream_iterator. Итераторы вывода (output iterators) устроены аналогично, но служат для вывода: перемещаются только вперед, по одному шагу за раз, позволяют записывать лишь в то место, на которое указывают, причем записать можно только один раз. Они моделируют указатель записи в выходной файл. К этой категории относится итератор ostream_iterator. Это самые «слабые» категории итераторов. Поскольку итераторы ввода и вывода могут перемещаться только в прямом направлении и позволяют лишь читать или писать туда, куда указывают, причем лишь единожды, они подходят только для однопроходных алгоритмов.

Более мощная категория итераторов состоит из однонаправленных итераторов (forward iterators). Такие итераторы могут делать все, что делают итераторы ввода и вывода, плюс разрешают читать и писать в то место, на которое указывают, более одного раза. Это делает их удобными для многопроходных алгоритмов. STL не предоставляет реализацию однонаправленных связных списков, но в некоторых библиотеках они есть (и обычно называются slist); итераторы таких контейнеров являются однонаправленными. Итераторы кэшированных контейнеров в библиотеке TR1 (см. правило 54) также могут быть однонаправленными.

Двунаправленные итераторы (bidirectional iterators) добавляют к функциональности однонаправленных итераторов возможность перемещения назад. Итераторы для STL-контейнера list относятся к этой категории, равно как и итераторы для set, multiset, map и multimap.

Наиболее мощная категория итераторов – это итераторы с произвольным доступом (random access iterators). Итераторы этого типа добавляют к функциям двунаправленных итераторов «итераторную арифметику», то есть возможность перемещения вперед и назад на заданное расстояние, затрачивая на это постоянное время. Такая арифметика аналогична арифметике указателей, что неудивительно, поскольку итераторы с произвольным доступом моделируют встроенные указатели, а встроенные указатели могут вести себя как итераторы с произвольным доступом. Итераторы для vector, deque и string являются итераторами с произвольным доступом.

Для каждой из пяти категорий итераторов C++ в стандартной библиотеке имеется соответствующая «структура-тэг» (tag struct):

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag: public input_iterator_tag {};

struct bidirectional_iterator_tag: public forward_iterator_tag {};

struct random_access_iterator_teg: public bidirectional_iterator_tag {};

Отношения наследования между этими структурами корректно выражают взаимосвязь типа «является» (см. правило 32): верно, что все однонаправленные итераторы являются также итераторами ввода и т. д. Вскоре мы увидим примеры использования такого наследования.

Но вернемся к операции advance. Поскольку у разных итераторов возможности различны, то можно было при реализации advance воспользоваться «наименьшим общим знаменателем», то есть организовать цикл, в котором итератор увеличивается или уменьшается на единицу. Но такой подход требует линейных затрат времени. Итераторы с произвольным доступом обеспечивают доступ к любому элементу контейнера за постоянное время, и, конечно, мы бы хотели воспользоваться этим преимуществом, коль скоро оно имеется.

В действительности хотелось бы реализовать advance как-то так:

template<typename IterT, typename DistT>

void advance(IterT& iter, DistT d)

{

if (iter является итератором с произвольным доступом) {

iter += d; // использовать итераторную арифметику

} // для итераторов с произвольным доступом

else {

if(d>=0) {while (d–) ++iter;} // вызывать ++ или – в цикле

else {while(d++) –iter;} // для итераторов других категорий

}

}

Но для этого нужно уметь определять, является ли iter итератором с произвольным доступом, что, в свою очередь, требует знания о том, что его тип – IterT – относится к категории итераторов с произвольным доступом. Другими словами, нам нужно получить некоторую информацию о типе. Именно для этого и служат характеристики (traits): получить информацию о типе во время компиляции.