v = v2; // присваиваем другой вектор; v — теперь копия v2
// теперь v.size() == v2.size()
Стандартный библиотечный класс
vector
содержит и другие операции, которые могут изменять размер вектора, например
erase()
и
insert()
(раздел Б.4.7), но здесь мы просто покажем, как можно реализовать три указанные операции над вектором.
19.2.1. Представление
В разделе 19.1 мы продемонстрировали простейшую стратегию изменения размера: выделить память для нового количества элементов и скопировать туда старые элементы. Но если размер контейнера изменяется часто, то такая стратегия становится неэффективной. На практике, однажды изменив размер, мы обычно делаем это много раз. В частности, в программах редко встречается одиночный вызов функции
push_back()
.
Итак, мы можем оптимизировать наши программы, предусмотрев изменение размера контейнера. На самом деле все реализации класса
vector
отслеживают как количество элементов, так и объем свободной памяти, зарезервированной для будущего расширения. Рассмотрим пример.
class vector {
int sz; // количество элементов
double* elem; // адрес первого элемента
int space; // количество элементов плюс свободная
// память/слоты
// для новых элементов (текущая память)
public:
// ...
};
Эту ситуацию можно изобразить графически.
Поскольку нумерация элементов начинается с нуля, мы показываем, что переменная
sz
(количество элементов) ссылается на ячейку, находящуюся за последним элементом, а переменная
space
ссылается на ячейку, расположенную за последним слотом. Им соответствуют указатели, установленные на ячейки
elem+sz
и
elem+space
.
Когда вектор создается впервые, переменная
space
равна
sz
, т.е. “свободного места” нет.
Мы не начинаем выделение дополнительных слотов, пока количество элементов не изменится. Обычно это происходит, когда выполняется условие
space==sz
. Благодаря этому, используя функцию
push_back()
, мы не выходим за пределы памяти.
Конструктор по умолчанию (создающий объект класса
vector
без элементов) устанавливает все три члена класса равными нулю.
vector::vector():sz(0),elem(0),space(0) { }
Эта ситуация выглядит следующим образом:
“Запредельный элемент” является лишь умозрительным. Конструктор по умолчанию не выделяет свободной памяти и занимает минимальный объем (см. упр. 16). Наш класс
vector
иллюстрирует прием, который можно использовать для реализации стандартного вектора (и других структур данных), но стандартные библиотечные реализации отличаются большим разнообразием, поэтому вполне возможно, что в вашей системе класс
std::vector
использует другие стратегии.
19.2.2. Функции reserve и capacity
Самой главной операцией при изменении размера контейнера (т.е. при изменении количества элементов) является функция
vector::reserve()
. Она добавляет память для новых элементов.
void vector::reserve(int newalloc)
{
if (newalloc<=space) return; // размер не уменьшается
double* p = new double[newalloc]; // выделяем новую память
for (int i=0; i<sz; ++i) p[i] = elem[i]; // копируем старые
// элементы
delete[] elem; // освобождаем старую память
elem = p;
space = newalloc;
}
Обратите внимание на то, что мы не инициализировали элементы в выделенной памяти. Мы просто резервируем память, а как ее использовать — задача функций
push_back()
и
resize()
.
Очевидно, что пользователя может интересовать размер доступной свободной памяти в объекте класса
vector
, поэтому, аналогично стандартному классу, мы предусмотрели функцию-член, выдающую эту информацию.
int vector::capacity() const { return space; }
Иначе говоря, для объекта класса
vector
с именем
v
выражение
v.capacity()–v.size()
возвращает количество элементов, которое можно записать в объект
v
с помощью функции
push_back()
без выделения дополнительной памяти.
19.2.3. Функция resize
Имея функцию
reserve()
, реализовать функцию
resize()
для класса
vector
не представляет труда. Необходимо предусмотреть несколько вариантов.
• Новый размер больше ранее выделенной памяти.
• Новый размер больше прежнего, но меньше или равен ранее выделенной памяти.
• Новый размер равен старому.
• Новый размер меньше прежнего.
Посмотрим, что у нас получилось.
void vector::resize(int newsize)
// создаем вектор, содержащий newsize элементов
// инициализируем каждый элемент значением 0.0 по умолчанию
{
reserve(newsize);
for (int i=sz; i<newsize; ++i) elem[i] = 0; // инициализируем
