Стенли Липпман - Язык программирования C++. Пятое издание

• указатель elementsна первый элемент в зарезервированной памяти;

• указатель first_freeна следующий элемент после фактически последнего;

• указатель capна следующий элемент после конца зарезервированной памяти.

Значение этих указателей представлено на рис. 13.2.

Рис. 13.2. Стратегия резервирования памяти класса StrVec

Кроме этих указателей, класс StrVecбудет иметь переменную-член allocтипа allocatorдля резервирования памяти, используемой классом StrVec. У класса также будет четыре вспомогательных функции.

• Функция alloc_n_copy()будет резервировать пространство и копировать заданный диапазон элементов.

• Функция free()будет удалять созданные элементы и освобождать пространство.

• Функция chk_n_alloc()будет гарантировать наличие достаточного места для добавления по крайней мере еще одного элемента в вектор StrVec. Если места для следующего элемента нет, то функция chk_n_alloc()вызовет функцию reallocate()для резервирования большего пространства.

• Функция reallocate()будет пересоздавать вектор StrVec, когда прежнее пространство окажется исчерпано.

Хотя основное внимание уделено реализации, определим также несколько членов из интерфейса класса vector.

Теперь, сделав набросок реализации, можно определить класс StrVec:

// упрощенная реализация стратегии резервирования памяти для подобного

// вектору класса

class StrVec {

public:

StrVec(): // член allocator инициализируется по умолчанию

elements(nullptr), first_free(nullptr), cap(nullptr) { }

StrVec(const StrVec&); // конструктор копий

StrVec &operator=(const StrVec&); // присвоение копии

~StrVec(); // деструктор

void push_back(const std::string&); // копирует элемент

size_t size() const { return first_free - elements; }

size_t capacity() const { return cap - elements; }

std::string *begin() const { return elements; }

std::string *end() const { return first_free; }

// ...

private:

std::allocator alloc; // резервирует элементы

// используется функциями, которые добавляют элементы в StrVec

void chk_n_alloc()

{ if (size() == capacity()) reallocate(); }

// вспомогательные члены, используемые конструктором копий,

// оператором присвоения и деструктором

std::pair alloc_n_copy

(const std::string*, const std::string*);

void free(); // удаляет элементы и освобождает пространство

void reallocate(); // резервирует больше места и копирует

// существующие элементы

std::string *elements; // указатель на первый элемент массива

std::string *first_free; // указатель на первый свободный

// элемент массива

std::string *cap; // указатель на следующий элемент после

// конца массива

};

Тело класса определяет некоторые из своих членов.

• Стандартный конструктор (неявно) инициализирует по умолчанию переменную-член allocи (явно) инициализирует указатели как nullptr, означая, что никаких элементов нет.

• Функция-член size()возвращает количество фактически используемых элементов, соответствует значению first_free - elements.

• Функция-член capacity()возвращает количество элементов, которые может содержать объект класса StrVec, соответствует значению cap - elements.

• Функция-член chk_n_alloc()приводит к пересозданию объекта класса StrVec, когда больше нет места для добавления следующего элемента. Это происходит при cap == first_free.

• Функции-члены begin()и end()возвращают указатели на первый (т.е. elements) и следующий после последнего существующего элемент (т.е. first_free) соответственно.

Функция push_back()вызывает функцию chk_n_alloc(), чтобы удостовериться в наличии места для элемента. В случае необходимости функция chk_n_alloc()вызовет функцию reallocate(). После вызова функции chk_n_alloc()функция push_back()знает, что место для нового элемента есть. Она запрашивает свой член класса allocatorсоздать новый последний элемент:

void StrVec::push_back(const string& s) {

chk_n_alloc(); // удостовериться в наличии места для другого элемента

// создать копию s в элементе, на который указывает first_free

alloc.construct(first_free++, s);

}

При использовании класса allocatorдля резервирования памяти следует помнить, что память резервируется пустой (см. раздел 12.2.2). Чтобы использовать эту память, следует вызвать функцию construct(), которая создаст объект в этой памяти. Первый аргумент функции construct()— это указатель на пустое пространство, зарезервированное вызовом функции allocate(). Остальные аргументы определяют, какой конструктор использовать при создании объекта в этом пространстве. В данном случае есть только один дополнительный аргумент типа string, поэтому этот вызов использует строковый конструктор копий.

Следует заметить, что вызов функции construct()осуществляет приращение указателя first_free, чтобы он снова указывал на элемент, который предстоит создать. Поскольку используется постфиксный инкремент (см. раздел 4.5), этот вызов создает объект в текущей позиции указателя first_free, а инкремент переводит его на следующий пустой элемент.

Функция-член alloc_n_copy()вызывается при копировании или присвоении объекта класса StrVec. У класса StrVecбудет подобное значению поведение (см. раздел 13.2.1), как у вектора; при копировании или присвоении объекта класса StrVecнеобходимо зарезервировать независимую память и скопировать элементы из оригинала в новый объект класса StrVec.

Функция-член alloc_n_copy()будет резервировать достаточно места для содержания заданного диапазона элементов, а затем копировать эти элементы во вновь созданное пространство. Эта функция возвращает значение типа pair(см. раздел 11.2.3), переменные-члены которого являются указателем на начало нового пространства и следующую позицию после последнего скопированного элемента:

pair

StrVec::alloc_n_copy(const string *b, const string *e) {

// резервировать пространство для содержания элементов диапазона

auto data = alloc.allocate(е - b);

// инициализировать и возвратить пару, созданную из данных,

// возвращенных функцией uninitialized_copy()

return {data, uninitialized_copy(b, e, data)};

}

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