Программирование. Принципы и практика использования C++ Исправленное издание
вернуться

Страуструп Бьерн
Шрифт:

vector<double> vd;

double d;

while(cin>>d) vd.push_back(d);

Насколько распространенным является изменение размера контейнера? Если такая ситуация встречается редко, то предусматривать для этого специальные средства было бы нецелесообразно. Однако изменение размера встречается очень часто. Наиболее очевидный пример — считывание неизвестного количества значений из потока ввода. Другими примерами являются коллекционирование результатов поиска (нам ведь неизвестно заранее, сколько их будет) и удаление элементов из коллекции один за другим. Таким образом, вопрос заключается не в том, стоит ли предпринимать изменение размера контейнера, а в том, как это сделать.

Почему мы вообще затронули тему, посвященную изменению размера контейнера? Почему бы просто не выделить достаточно памяти и работать с нею?! Эта стратегия выглядит наиболее простой и эффективной. Тем не менее это оправдано лишь в том случае, если мы не запрашиваем слишком много памяти. Программисты, избравшие эту стратегию, вынуждены переписывать свои программы (если они внимательно и систематически отслеживают переполнение памяти) или сталкиваются с катастрофическими последствиями (если они пренебрегли проверкой переполнения памяти).

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

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; // количество элементов плюс свободная