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

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

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

Определение класса StrVec

Теперь, сделав набросок реализации, можно определить класс 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<std::string> alloc; // резервирует элементы

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

 void chk_n_alloc()

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

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

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

 std::pair<std::string*, std::string*> 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) соответственно.

Использование функции-члена construct()

Функция 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()

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

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

pair<string*, string*>

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() вычисляет объем резервируемого пространства, вычитая указатель на первый элемент из указателя на следующий после последнего. Зарезервировав память, функция создает в ней копии заданных элементов.

Копирование осуществляется в операторе return при списочной инициализации возвращаемого значения (см. раздел 6.3.2). Указатель-член first возвращенной пары указывает на начало зарезервированной памяти; значение для указателя-члена second возвращается функцией uninitialized_copy() (см. раздел 12.2.2). Это значение будет указателем на следующий элемент после последнего созданного элемента.

Функция-член free()

У функции-члена free() две обязанности: она должна удалить элементы, а затем освободить пространство, зарезервированное объектом класса StrVec. Цикл for вызывает функцию destroy() класса allocator, перебирая элементы в обратном порядке, начиная с последнего существующего элемента и заканчивая первым:

void StrVec::free() {

 // нельзя освободить 0 указателей;

 // если элемент нулевой - не делать ничего

 if (elements) {

  // удалить прежние элементы в обратном порядке

  for (auto p = first_free; p != elements; /* пусто */)

   alloc.destroy(--p);

  alloc.deallocate(elements, cap - elements);

 }

}

Функция destroy() запускает деструктор класса string. Деструктор класса string освобождает память, занятую самой строкой.

Как только элементы будут удалены, освобождается пространство, зарезервированное классом StrVec при вызове функции deallocate(). Указатель, передаваемый функции deallocate(), должен быть именно тем, который ранее создал вызов функции allocate(). Поэтому перед вызовом функции deallocate() сначала проверяется, тот ли это elements, а не нулевой.

Функции-члены управления копированием

При наличии функций-членов alloc_n_copy() и free() функции-члены управления копированием нашего класса очень просты.

StrVec::StrVec(const StrVec &s) {

 // вызов функции alloc_n_copy() для резервирования количества

 // элементов как в s

 auto newdata = alloc_n_copy(s.begin(), s.end());

 elements = newdata.first;

 first_free = cap = newdata.second;

}

Конструктор копий вызывает функцию alloc_n_copy(), а затем присваивает результат вызова переменным-членам. Возвращаемое значение функции alloc_n_copy() является парой указателей. Первый указатель указывает на первый созданный элемент, а второй — на следующий после последнего созданного. Поскольку функция alloc_n_copy() резервирует пространство для точно такого количества элементов, которое было задано, указатель cap также указывает только на следующий после последнего созданного.