Д. Стефенс - C++. Сборник рецептов

Поймите, как реализован vector, узнайте о сложности методов вставки и удаления и минимизируйте ненужные операции с памятью с помощью метода reserve. Пример 6.2 показывает некоторые из этих методик в действии.

Пример 6.2. Эффективное использование vector

#include

#include

#include

using std::vector;

using std::string;

void f(vector& vec) {

// Передача vec по ссылке (или,

// если требуется, через указатель)

// ...

}

int main() {

vector vec(500); // При создании vector говорим, что в него

// планируется поместить определенное количество

// объектов

vector vec2;

// Заполняем vec...

f(vec);

vec2 reserve(500); // Или постфактум говорим vector,

// что требуется буфер достаточно большого

// размера для хранения объектов

// Заполняем vec2...

}

Ключ к эффективному использованию vectorлежит в знании его работы. Когда у вас есть четкое представление реализации vector, вопросы производительности становятся очевидными.

vector— это по сути управляемый массив. Более конкретно, vector— это непрерывный фрагмент памяти (т.е. массив), который достаточно велик для хранения n объектов типа T, где n больше или равно нулю и меньше или равно зависящему от реализации максимальному размеру. Обычно n увеличивается в процессе жизни контейнера при добавлении или удалении элементов, но оно никогда не уменьшается. Что отличает vectorот массива — это автоматическое управление памятью массива, методы для вставки и получения элементов и методы, которые предоставляют метаданные о контейнере, такие как размер (число элементов) и емкость (размер буфера), а также информацию о типе: vector::value_type— это тип T, vector::pointer— это тип указатель-на- Tи т.д. Два последних и некоторые другие являются частью любого стандартного контейнера, и они позволяют писать обобщенный код, который работает независимо от типа T. Рисунок 6.1 показывает графическое представление того, что предоставляют некоторые из методов vector, если vectorимеет размер 7 и емкость 10.

Рис. 6.1. Внутренности vector

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

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

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