C++. Сборник рецептов полностью

Если вам любопытно, как поставщик вашей стандартной библиотеки реализовал vector, скомпилируйте пример 6.1 и пройдите в отладчике все вызовы методов vector или откройте заголовочный файл реализации стандартной библиотеки и изучите его. Код, который вы там увидите, по большей части не является дружественным к читателю, но он должен осветить некоторые моменты. Во-первых, если вы еще не видели кода библиотеки, он даст вам представление о методиках реализации, используемых для написания эффективного, переносимого обобщенного кода. Во-вторых, он даст точное представление о том, что представляют собой используемые вами контейнеры. При написании кода, который должен работать с различными реализациями стандартной библиотеки, это следует сделать в любом случае.

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

Обычно добавление объекта T в следующий доступный слот буфера выполняется с помощью копирующего конструктора и new, которому передается тип создаваемого объекта, а также адрес, по которому он должен быть создан. Если вместо этого явно присвоить значение слоту, используя его индекс (с помощью operator[] или at), то будет использован оператор присвоения T. Заметьте, что в обоих случаях объект клонируется либо с помощью конструктора копирования, либо T::operator=. vector не просто хранит адрес добавляемого объекта. Именно по этой причине любой тип, сохраняемый в векторе, должен поддерживать копирующий конструктор и присвоение. Эти свойства означают, что эквивалентный объект типа T может быть создан с помощью вызова конструктора копирования T или оператора присвоения. Это очень важно из-за семантики копирования vector — если конструктор копирования или присвоение объектов не работает, то результаты, получаемые из vector, могут отличаться от того, что в него помещалось. А это плохо.

После добавления некоторого набора объектов в vector его буфер заполняется, и для добавления новых объектов его требуется увеличить. Алгоритм увеличения размера зависит от реализации, но обычно буфер размера n увеличивается до 2n+1. Важным здесь является то, как vector увеличивает свой буфер. Вы не можете просто сказать операционной системе неопределенно увеличить свой фрагмент памяти кучи. Требуется запросить новый фрагмент, который больше уже имеющегося. В результате процесс увеличения размера буфера выглядит следующим образом.

1. Выделить память для нового буфера.

2. Скопировать старые данные в новый буфер.

3. Удалить старый буфер.

Это позволяет vector хранить все его объекты в одном непрерывном фрагменте памяти.

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

Для начала, vector (или любой другой контейнер из стандартной библиотеки) не хранит объекты. Он хранит копии объектов. Это значит, что каждый раз, когда в vector заносится новый объект, он туда не «кладется». С помощью конструктора копирования или оператора присвоения он копируется в другое место. Аналогично при получении значения из vector происходит копирование того, что находится в векторе по указанному индексу, в локальную переменную. Рассмотрим простое присвоение элемента vector локальной переменной.

vector myVec;

// Поместить несколько объектов MyObj в myVec

MyObj obj = myVec[10]; // Скопировать объект с индексом 10

Это присвоение вызывает оператор присвоения obj, в качестве правого операнда которого используется объект, возвращенный myVec[10]. Накладные расходы на производительность при работе с большим количеством объектов резко возрастают, так что их лучше всего избегать.

Для снижения накладных расходов на копирование вместо помещения в vector самих объектов поместите в него указатели. Сохранение указателей потребует меньшего количества циклов ЦП на добавление и получение данных, так как указатели проще скопировать, чем объекты, и, кроме того, это снизит объем памяти, необходимый для буфера vector. Но помните, что при добавлении в контейнер стандартной библиотеки указателей контейнер не удаляет их при своем уничтожении. Контейнеры удаляют только содержащиеся в них объекты, т.е. переменные, которые хранят адреса объектов, но контейнер ничего не знает, хранится ли в нем указатель или объект. Все, что он знает, — это то, что это объект типа T.