эффективной. Тем не менее это оправдано лишь в том случае, если мы не запрашиваем слишком много памяти. Программисты, избравшие эту стратегию, вынуждены переписывать свои программы (если они внимательно и систематически отслеживают переполнение памяти) или сталкиваются с катастрофическими последствиями (если они пренебрегли проверкой переполнения памяти).
Очевидно, что объекты класса vector должны хранить числа с двойной точностью, значения температуры, записи (разного вида), строки, операции, кнопки графического пользовательского интерфейса, фигуры, даты, указатели на окна и т.д. Перечисление можно продолжать бесконечно. Контейнеры тоже бывают разного вида. Это важное обстоятельство, имеющее значительные последствия, которое обязывает нас хорошенько подумать, прежде чем выбрать конкретный вид контейнера. Почему не все контейнеры представляют собой векторы? Если бы мы имели дело только с одним видом контейнера, то операции над ним можно было бы сделать частью языка программирования. Кроме того, нам не пришлось бы возиться с другими видами контейнеров; мы бы просто всегда использовали класс vector.
Структуры данных играют ключевую роль в большинстве важных приложений. О том, как организовать данные, написано множество толстых и полезных книг. В большинстве из них рассматривается вопрос: “Как лучше хранить данные?” Ответ один — нам нужны многочисленные и разнообразные контейнеры, однако это слишком обширная тема, которую в этой книге мы не можем осветить в должной мере. Тем не менее мы уже широко использовали классы vector и string (класс string — это контейнер символов). В следующих главах мы опишем классы list, map (класс map — это дерево, в котором хранятся пары значений) и матрицы. Поскольку нам нужны разнообразные контейнеры, для их поддержки необходимы соответствующие средства языка и технологии программирования. Технологии хранения данных и организации доступа к ним являются одними из наиболее фундаментальных и наиболее сложных форм вычислений.
На уровне машинной памяти все объекты имеют фиксированный размер и не имеют типов. Здесь мы рассматриваем средства языка и технологии программирования, позволяющие создавать контейнеры объектов разного типа с переменным количеством элементов. Это обеспечивает значительную гибкость программ и удобство программирования.
19.2. Изменение размера
Какие возможности для изменения размера имеет стандартный библиотечный класс vector? В нем предусмотрены три простые операции. Допустим, в программе объявлен следующий объект класса vector:
vector<double> 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<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() для класса
