class="code">vector не представляет труда. Необходимо предусмотреть несколько вариантов.
• Новый размер больше ранее выделенной памяти.
• Новый размер больше прежнего, но меньше или равен ранее выделенной памяти.
• Новый размер равен старому.
• Новый размер меньше прежнего.
Посмотрим, что у нас получилось.
void vector::resize(int newsize)
// создаем вектор, содержащий newsize элементов
// инициализируем каждый элемент значением 0.0 по умолчанию
{
reserve(newsize);
for (int i=sz; i<newsize; ++i) elem[i] = 0; // инициализируем
// новые элементы
sz = newsize;
}
Основная работа с памятью поручена функции reserve(). Цикл инициализирует новые элементы (если они есть).
Мы не выделяли каждый из этих вариантов явно, но, как легко проверить, все они, тем не менее, обработаны правильно.
ПОПРОБУЙТЕ
Какие варианты следует предусмотреть (и протестировать), если мы хотим убедиться, что данная функция resize() работает правильно? Что скажете об условиях newsize==0 и newsize==–77?
19.2.4. Функция push_back
При первом рассмотрении функция push_back() может показаться сложной для реализации, но функция reserve() все упрощает.
void vector::push_back(double d)
// увеличивает размер вектора на единицу;
// инициализирует новый элемент числом d
{
if (space==0) reserve(8); // выделяет память для 8
// элементов
else if (sz==space) reserve(2*space); // выделяет дополнительную
// память
elem[sz] = d; // добавляет d в конец вектора
++sz; // увеличивает размер (sz — количество элементов)
}
Другими словами, если у нас нет свободной памяти, то удваиваем размер выделенной памяти. На практике эта стратегия оказывается очень удачной, поэтому она используется в стандартном библиотечном классе vector.
19.2.5. Присваивание
Присваивание векторов можно определить несколькими способами. Например, мы могли бы допускать присваивание, только если векторы имеют одинаковое количество элементов. Однако в разделе 18.2.2 мы решили, что присваивание векторов должно иметь более общий характер и более очевидный смысл: после присваивания v1=v2 вектор v1 является копией вектора v2 . Рассмотрим следующий рисунок.
Очевидно, что мы должны скопировать элементы, но есть ли у нас свободная память? Можем ли мы скопировать вектор в свободную память, расположенную за его последним элементом? Нет! Новый объект класса vector будет хранить копии элементов, но поскольку мы еще не знаем, как он будет использоваться, то не выделили свободной памяти в конце вектора.
Простейшая реализация описана ниже.
• Выделяем память для копии.
• Копируем элементы.
• Освобождаем старую память.
• Присваиваем членам sz, elem и space новые значения.
Код будет выглядеть примерно так:
vector& vector::operator=(const vector& a)
// похож на конструктор копирования,
// но мы должны работать со старыми элементами
{
double* p = new double[a.sz]; // выделяем новую память
for (int i = 0; i<a.sz; ++i) p[i] = a.elem[i]; // копируем
// элементы
delete[] elem; // освобождаем старую память
space = sz = a.sz; // устанавливаем новый размер
elem = p; // устанавливаем новые элементы
return *this; // возвращаем ссылку на себя
}
Согласно общепринятому соглашению оператор присваивания возвращает ссылку на целевой объект. Смысл выражения *this объяснялся в разделе 17.10. Его реализация является корректной, но, немного поразмыслив, легко увидеть, что мы выполняем избыточные операции выделения и освобождения памяти. Что делать, если целевой вектор содержит больше элементов, чем присваиваемый вектор? Что делать, если целевой вектор содержит столько же элементов, сколько и присваиваемый вектор? Во многих приложениях последняя ситуация встречается чаще всего. В любом случае мы можем просто скопировать элементы в память, уже выделенную ранее целевому вектору.
vector& vector::operator=(const vector& a)
{
if (this==&a) return *this; // самоприсваивание, ничего делать
// не надо
if (a.sz<=space) { // памяти достаточно, новая память
// не нужна
for (int i = 0; i<a.sz; ++i) elem[i] = a.elem[i]; // копируем
sz = a.sz;
return *this;
}
double* p = new double[a.sz]; // выделяем новую память
for (int i = 0; i<a.sz; ++i) p[i] = a.elem[i]; // копируем
// элементы
delete[] elem; // освобождаем старую память
space = sz = a.sz; // устанавливаем новый размер
elem = p; // устанавливаем указатель на новые
// элементы
return *this; // возвращаем ссылку на целевой объект
}
В этом фрагменте кода мы сначала проверяем самоприсваивание (например, v=v); в этом случае ничего делать не надо. С логической точки зрения эта проверка лишняя, но иногда она позволяет значительно оптимизировать программу. Эта проверка демонстрирует использование указателя this, позволяющего проверить, является ли аргумент a тем же объектом, что и объект, из которого вызывается функция-член (т.е. operator=()). Убедитесь, что этот код действительно работает, если из него удалить инструкцию this==&a. Инструкция a.sz<=space также включена для оптимизации. Убедитесь, что этот код действительно работает после удаления из него инструкции a.sz<=space.
19.2.6. Предыдущая версия класса vector
Итак, мы получили почти реальный класс vector для чисел типа double.
// почти реальный вектор чисел типа double
class vector {
/*
инвариант:
для 0<=n<sz значение elem[n] является n- м элементом
sz<=space;
если sz<space, то после elem[sz–1] есть место
для (space–sz) чисел типа double
*/
int sz; // размер
double* elem; // указатель на элементы (или 0)
int space; // количество элементов плюс количество слотов
public:
vector():sz(0),elem(0),space(0) { }
explicit vector(int s):sz(s),elem(new double[s]),space(s)
{
for (int i=0; i<sz; ++i) elem[i]=0; // элементы
// инициализированы
}
vector(const vector&); // копирующий конструктор
vector& operator=(const vector&); // копирующее присваивание
~vector() { delete[] elem; } // деструктор
double& operator[ ](int n) { return elem[n]; } // доступ
const double& operator[](int n) const { return elem[n]; }
