C++. Сборник рецептов

Когсуэлл Джефф

Также

vector

предоставляет безопасность, которой просто невозможно достичь в случае обычных массивов. В отличие от массивов

vector

с помощью метода

at

предлагает проверку диапазонов. Если в

at

передается неправильный индекс, он выбрасывает исключение

out_of_range

, которое затем можно перехватить с помощью

catch

и адекватно на него отреагировать. Например:

try {

 intVec.at(300) = 2;

} catch(std::out_of_range& e) {

 std::cerr << "out_of_range: " << e.what << std::endl;

}

Как

вы знаете, если обратиться к элементу за пределами массива с помощью

operator[]

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

operator[]

для vector работает точно так же, но когда требуется обезопасить код, используйте

at

.

Итак, вот краткий курс по

vector

. Но что такое

vector

? Если вы используете С++, то вас, вероятно, волнуют проблемы производительности, и вам не понравится, если вам просто дадут что-то и скажут, что это работает. Вполне справедливо. За обсуждением работы

vector

и советами по его эффективному использованию обратитесь к рецепту 6.2.

Смотри также

Рецепт 6.2.

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

Проблема

Вы используете

vector

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

Решение

Поймите, как реализован

vector

, узнайте о сложности методов вставки и удаления и минимизируйте ненужные операции с памятью с помощью метода

reserve

. Пример 6.2 показывает некоторые из этих методик в действии.

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

#include <iostream>

#include <vector>

#include <string>

using std::vector;

using std::string;

void f(vector<string>& vec) {

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

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

 // ...

}

int main {

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

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

// объектов

 vector<string> vec2;

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

 f(vec);

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

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

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

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

}

Обсуждение

Ключ к эффективному использованию

vector

лежит в знании его работы. Когда у вас есть четкое представление реализации

vector

, вопросы производительности становятся очевидными.

Как работает vector

vector

— это по сути управляемый массив. Более конкретно,

vector<T>

— это непрерывный фрагмент памяти (т.е. массив), который достаточно велик для хранения n объектов типа

T

,

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

vector

от массива — это автоматическое управление памятью массива, методы для вставки и получения элементов и методы, которые предоставляют метаданные о контейнере, такие как размер (число элементов) и емкость (размер буфера), а также информацию о типе:

vector<T>::value_type

— это тип

T

,

vector<T>::pointer

— это тип указатель-на-

T

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

T

. Рисунок 6.1 показывает графическое представление того, что предоставляют некоторые из методов

vector

, если

vector

имеет размер 7 и емкость 10.

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

Если вам любопытно, как поставщик вашей стандартной библиотеки реализовал

vector

, скомпилируйте пример 6.1 и пройдите в отладчике все вызовы методов vector или откройте заголовочный файл

<vector>

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

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

T

, и элементы, добавляемые или присваиваемые вами, с помощью конструктора копирования или операции присвоения помешаются в элементы этого массива.

Обычно добавление объекта

T

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

operator[]

или

at

), то будет использован оператор присвоения

T

. Заметьте, что в обоих случаях объект клонируется либо с помощью конструктора копирования, либо

T::operator=

.

vector

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

T

может быть создан с помощью вызова конструктора копирования

T

или оператора присвоения. Это очень важно из-за семантики копирования

vector

— если конструктор копирования или присвоение объектов не работает, то результаты, получаемые из vector, могут отличаться от того, что в него помещалось. А это плохо.

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