Программирование

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

19.2. Изменение размера

Какие возможности для изменения размера имеет стандартный библиотечный класс vector? В нем предусмотрены три простые операции. Допустим, в программе объявлен следующий объект класса vector:

vector v(n); // v.size()==n

Изменить его размер можно тремя способами.

v.resize(10);    // v теперь имеет 10 элементов

v.push_back(7);  // добавляем элемент со значением 7 в конец объекта v

                 // размер v.size() увеличивается на единицу

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

                                           // элементы

  delete[] elem;    // освобождаем старую память

  elem = p;

  space = newalloc;

}

Обратите внимание на то, что мы не инициализировали элементы в выделенной памяти. Мы просто резервируем память, а как ее использовать — задача функций push_back() и resize().