Эффективное использование STL

В контейнерах хранятся объекты, но не те, которые вы им передаете. Более того, при получении объекта из контейнера вам предоставляется не тот объект, который находился в контейнере. При включении объекта (вызовом insert, push_back и т. д.) в контейнер заносится копия указанного объекта. При получении объекта из контейнера (например, вызовом front или back) вы также получаете копию. Копирование на входе, копирование на выходе — таковы правила STL.

Но и после того, как объект окажется в контейнере, он может участвовать в операциях копирования. В результате вставки или удаления элементов в vector, string и deque существующие элементы контейнера обычно перемещаются (копируются) в памяти (советы 5 и 14). Алгоритмы сортировки (совет 31), next_permutation и previous_permutation; remove, unique и их родичи (совет 32); rotate и reverse — все эти операции приводят к копированию объектов. Да, копирование объектов действительно занимает очень важное место в STL.

Возможно, вам будет интересно узнать, как же производится копирование. Очень просто — объект копируется вызовом соответствующих функций этого объекта, а точнее копирующего конструктора и копирующего оператора присваивания. В пользовательских классах эти функции обычно объявляются следующим образом:

class Widget{
public:
 Widget(const Widget&):// Копирующий конструктор
 Widget& operator=(const Widget&);// Копирующий оператор присваивания
 …
};

Как обычно, если вы не объявите эти функции самостоятельно, компилятор сделает это за вас. Встроенные типы (int, указатели и т. д.) копируются простым копированием их двоичного представления. Копирующие конструкторы и операторы присваивания описаны в любом учебнике по C++. В частности, эти функции рассмотрены в советах 11 и 27 книги «Effective C++».

Теперь вам должен быть ясен смысл этого совета. Если контейнер содержит объекты, копирование которых сопряжено с большими затратами, простейшее занесение объектов в контейнер может заметно повлиять на скорость работы программы. Чем больше объектов перемещается в контейнере, тем больше памяти и тактов процессора расходуется на копирование. Более того, у некоторых объектов само понятие «копирование» имеет нетрадиционный смысл, и при занесении таких объектов в контейнер неизменно возникают проблемы (пример приведен в совете 8).

В ситуациях с наследованием копирование становится причиной отсечения. Иначе говоря, если создать контейнер объектов базового класса и попытаться вставить в него объекты производного класса, «производность» этих объектов утрачивается при копировании объектов (копирующим конструктором базового класса) в контейнер:

vector<Widget> vw;
class Special Widget: // SpecialWidget наследует от класса
 public Widget{...}; // Widget (см. ранее)
SpecialWidget sw; // sw копируется в vw как объект базового класса
vw.push_back(sw); // Специализация объекта теряется (отсекается)

Проблема отсечения предполагает, что вставка объекта производного класса в контейнер объектов базового класса обычно приводит к ошибке. А если вы хотите, чтобы полученный объект обладал поведением объекта производного класса (например, вызывал виртуальные функции объектов производного класса), вставка всегда приводит к ошибке. За дополнительной информацией обращайтесь к «Effective C++», совет 22. Другой пример проявления этой проблемы в STL описан в совете 38.

Существует простое решение, обеспечивающее эффективное, корректное и свободное от проблемы отсечения копирование — вместо объектов в контейнере хранятся указатели. Иначе говоря, вместо контейнера для хранения Widget создается контейнер для Widget*. Указатели быстро копируются, результат точно совпадает с ожидаемым (поскольку копируется базовое двоичное представление), а при копировании указателя ничего не отсекается. К сожалению, у контейнеров указателей имеются свои проблемы, обусловленные спецификой STL. Они рассматриваются в советах 7 и 33. Пытаясь справиться с этими проблемами и при этом не нажить хлопот с эффективностью, корректностью и отсечением, вы, вероятно, обнаружите симпатичную альтернативу — умные указатели. За дополнительной информацией обращайтесь к совету 7.

Если вам показалось, что STL злоупотребляет копированием, не торопитесь с выводами. Да, копирование в STL выполняется довольно часто, но в целом библиотека спроектирована с таким расчетом, чтобы избежать лишнего копирования. Более того, она избегает лишнего создания объектов. Сравните с поведением классического массива — единственного встроенного контейнера C и C++:

Widget w[maxNumWidgets]; // Создать массив объектов Widget
 // Объекты инициализируются конструктором
 // по умолчанию

В этом случае конструируются maxNumWidgets объектов Widget, даже если на практике будут использоваться лишь некоторые из них или все данные, инициализированные конструктором по умолчанию, будут немедленно перезаписаны данными, взятыми из другого источника (например, из файла). Вместо массива можно воспользоваться контейнером STL vector и создать вектор, динамически увеличивающийся в случае необходимости:

vector<Widget> vw; // Создать вектор, не содержащий ни одного
 // объекта Widget и увеличивающийся по мере
 // необходимости

Можно также создать пустой вектор, в котором зарезервировано место для maxNumWidgets объектов Widget, но не сконструирован ни один из этих объектов:

vector<Widget> vw;
vw.reserve(maxNumWidgets); // Функция reserve описана в совете 14

По сравнению с массивами контейнеры STL ведут себя гораздо цивилизованнее. Они создают (посредством копирования) столько объектов, сколько указано, и только по вашему требованию, а конструктор по умолчанию выполняется только с вашего разрешения. Да, контейнеры STL создают копии; да, в особенностях их работы необходимо хорошо разбираться, но не стоит забывать и о том, что они означают большой шаг вперед по сравнению с массивами.

Совет 4. Вызывайте empty вместо сравнения size с нулем

Для произвольного контейнера с следующие две команды фактически эквивалентны:

if (c.size==0)...
if (c.empty)...

Возникает вопрос — почему же предпочтение отдается одной конструкции, особенно если учесть, что empty обычно реализуется в виде подставляемой (inline) функции, которая просто сравнивает size с нулем и возвращает результат?

Причина проста: функция empty для всех стандартных контейнеров выполняется с постоянной сложностью, а в некоторых реализациях list вызов size требует линейных затрат времени.