Язык программирования C Пятое издание
 Скачать 1.85 Mb.
|
Упражнение 13.36. Разработайте и реализуйте соответствующий класс Folder. Этот класс должен содержать набор указателей на сообщения в той папке. Упражнение 13.37. Добавьте в класс Message функции-члены удаления и вставки заданного Folder* в folders. Эти члены аналогичны функциям-членам addMsg() и remMsg() класса Folder. Упражнение 13.38. Для определения оператора присвоения класса Message не использовалась технология копирования и обмена. Почему, по вашему? 13.5. Классы, управляющие динамической памятью Некоторые классы должны резервировать переменный объем памяти во время выполнения. Такие классы зачастую способны (а если способны, то обычно обязаны) использовать библиотечный контейнер для хранения данных. Например, для хранения своих элементов класс StrBlob использует вектор. Но эта стратегия срабатывает не для каждого класса; некоторые из них должны самостоятельно резервировать память. Обычно такие классы определяют собственные функции-члены управления копированием, чтобы управлять памятью, которую они резервируют. В качестве примера реализуем упрощенную версию библиотечного класса vector. Кроме прочих упрощений, этот класс не будет шаблоном, он сможет хранить только строки. Поэтому назовем этот класс StrVec. Проект класса StrVec Как уже упоминалось, класс vector хранит свои элементы в непрерывном хранилище. Для повышения производительности класс vector предварительно резервирует хранилище, размер которого превосходит необходимое количество элементов (см. раздел 9.4). Каждая добавляющая элементы функция-член вектора проверяет наличие доступного пространства для следующего элемента. Если это так, элемент размещается в следующей доступной ячейке. Если места нет, вектор пересоздается: он резервирует новое пространство, перемещает в него существующие элементы, освобождает прежнее пространство и добавляет новый элемент. Подобную стратегию и будем использовать в классе StrVec. Для получения пустой памяти используем класс allocator (см. раздел 12.2.2). Поскольку резервируемая классом allocator память пуста, используем его функцию-член construct() для создания объектов в этом пространстве, когда необходимо добавить новый элемент. Точно так же при удалении элемента используем его функцию-член destroy(). У каждого объекта класса StrVec будет три указателя на пространство, используемое для хранения его элементов: • указатель elements на первый элемент в зарезервированной памяти; • указатель first_free на следующий элемент после фактически последнего; • указатель cap на следующий элемент после конца зарезервированной памяти. Значение этих указателей представлено на рис. 13.2. Page 656/1103 Рис. 13.2. Стратегия резервирования памяти класса StrVec Кроме этих указателей, класс StrVec будет иметь переменную-член alloc типа allocator<string> для резервирования памяти, используемой классом StrVec. У класса также будет четыре вспомогательных функции. • Функция alloc_n_copy() будет резервировать пространство и копировать заданный диапазон элементов. • Функция free() будет удалять созданные элементы и освобождать пространство. • Функция chk_n_alloc() будет гарантировать наличие достаточного места для добавления по крайней мере еще одного элемента в вектор StrVec. Если места для следующего элемента нет, то функция chk_n_alloc() вызовет функцию reallocate() для резервирования большего пространства. • Функция 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; } Page 657/1103 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; // Page 658/1103 указатель на следующий элемент после // конца массива }; Тело класса определяет некоторые из своих членов. • Стандартный конструктор (неявно) инициализирует по умолчанию переменную-член 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, а инкремент переводит его на следующий пустой элемент. Page 659/1103 Функция-член 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 указателей; Page 660/1103 // если элемент нулевой - не делать ничего 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 также указывает только на следующий после последнего созданного. Деструктор вызывает функцию free(): Page 661/1103 StrVec::StrVec() { free(); } Оператор присвоения копии вызывает функцию alloc_n_copy() прежде, чем освободить существующие элементы. Это защищает от копирования в себя самого: StrVec &StrVec::operator=(const StrVec &rhs) { // вызов alloc_n_copy() для резервирования точно такого количества // элементов, как в rhs auto data = alloc_n_copy(rhs.begin(), rhs.end()); free(); elements = data.first; first_free = cap = data.second; return *this; } Подобно конструктору копий, оператор присвоения копии использует значения, возвращенные функцией alloc_n_copy(), для инициализации своих указателей. Перемещение, а не копирование элементов при резервировании Прежде чем приступить к функции reallocate(), следует обдумать то, что она должна делать: • зарезервировать память для нового, большего массива строк; • заполнить первую часть этого пространства существующими элементами; • удалить элементы в существующей памяти и освободить ее. Глядя на этот список, можно заметить, что пересоздание объекта класса StrVec влечет за собой копирование каждой строки из прежнего объекта StrVec в новый. Даже без подробностей реализации класса string известно, что строки ведут себя подобно значению. После копирования новая строка и оригинальная независимы друг от друга. Изменения, внесенные в оригинал, не распространяются на копию, и наоборот. Поскольку строки действуют, как значения, можно сделать вывод, что у каждой строки должна быть собственная копия составляющих ее символов. Копирование строки должно резервировать память для этих символов, а удаление строки должно освободить используемую ею память. Копирование строки подразумевает копирование данных, поскольку обычно после копирования строки у нее будет два пользователя. Но когда функция reallocate() копирует строки объекта класса StrVec, у этих строк будет только один пользователь. Как только копирование элементов из прежнего пространства в новое завершается, исходные строки немедленно удаляются. Копирование данных этих строк не нужно. Производительность класса StrVec будет Page 662/1103 значительно выше , если удастся избежать дополнительных затрат на резервирование и освобождение строк при каждом его пересоздании.Конструктор перемещения и функция std::move() Копирования строки можно избежать при помощи двух средств, введенных новой библиотекой. Во-первых, некоторые из библиотечных классов, включая класс string, определяют так называемые конструкторы перемещения (move constructor). Подробности работы конструктора перемещения класса string (равно как и все остальные подробности его реализации) не раскрываются. Однако общеизвестно, что конструкторы перемещения обычно "перемещают" ресурсы из заданного объекта в создаваемый. Библиотека гарантирует также то, что "перемещенная" строка останется в допустимом состоянии. В случае класса string можно предположить, что у каждого его объекта есть указатель на массив типа char. По-видимому, конструктор перемещения класса string копирует указатель вместо резервирования нового пространства и копирования символов. Второе доступное для использования средство — это библиотечная функция move(), определенная в заголовке utility. Есть два важных момента, которые следует знать о функции move(). Во-первых, по причинам, рассматриваемым в разделе 13.6.1, когда функция reallocate() создает строки в новой области памяти, она должна вызвать функцию move(), чтобы сообщить о необходимости использования конструктора перемещения класса string. Если пропустить вызов функции move(), то будет использован конструктор копий класса string. Во-вторых, по причинам, рассматриваемым в разделе 18.2.3, объявление using (см. раздел 3.1) для функции move() обычно не предоставляется. Когда используется функция move(), вызывается функция std::move(), а не move(). Функция-член reallocate() Используя эту информацию, можно написать собственную функцию reallocate(). Сначала вызовем функцию allocate(), чтобы зарезервировать новое пространство. При каждом пересоздании объекта класса StrVec будем удваивать его емкость. Если вектор StrVec пуст, резервируем место для одного элемента: void StrVec::reallocate() { // будем резервировать вдвое больше элементов, чем текущий размер auto newcapacity = size() ? 2 * size() : 1; // резервировать новую память auto newdata = alloc.allocate(newcapacity); // переместить данные из прежней памяти в новую auto dest = newdata; // указывает на следующую свободную позицию в // новом массиве Page 663/1103 auto elem = elements; // указывает на следующий элемент в старом // массиве for (size_t i = 0; i != size(); ++i) alloc.construct(dest++, std::move(*elem++)); free(); // освобождает старое пространство после перемещения // элементов // обновить структуру данных, чтобы указать на новые элементы elements = newdata; first_free = dest; cap = elements + newcapacity; } Цикл for перебирает существующие элементы и создает соответствующие элементы в новом пространстве. Указатель dest используется для указания на область памяти, в которой создается новая строка, а указатель elem — для указания на элемент в оригинальном массиве. Для перемещения указателей dest и elem на следующий элемент этих двух массивов используем постфиксный инкремент. Второй аргумент в вызове функции construct() (т.е. аргумент, определяющий используемый конструктор (см. раздел 12.2.2)) является значением, возвращенным функцией move(). Вызов функции move() возвращает результат, заставляющий функцию construct() использовать конструктор перемещения класса string. Поскольку используется конструктор перемещения, управляемая память строки не будет скопирована. Вместо этого каждая создаваемая строка получит в собственность область памяти из строки, на которую указывает указатель elem. После перемещения элементов происходит вызов функции free() для удаления прежних элементов и освобождения памяти, которую данный вектор StrVec использовал перед вызовом функции reallocate(). Сами строки больше не управляют памятью, в которой они располагались; ответственность за их данные была передана элементам нового вектора StrVec. Нам неизвестно содержимое строк в памяти прежнего вектора StrVec, но нам гарантирована безопасность запуска деструктора класса string для этих объектов. Остается только обновить указатели адресами вновь созданного и инициализированного массива. Указатели first_free и cap обозначат элемент следующий после последнего созданного и следующий после последнего зарезервированного соответственно. Упражнения раздела 13.5 Упражнение 13.39. Напишите собственную версию класса StrVec, включая функции reserve(), Page 664/1103 capacity() (см. раздел 9.4) и resize() (см. раздел 9.3.5). Упражнение 13.40. Добавьте в класс StrVec конструктор, получающий аргумент типа initializer_list<string>. Упражнение 13.41. Почему в вызове функции construct() в функции push_back() был использован постфиксный инкремент? Что случилось бы при использовании префиксного инкремента? Упражнение 13.42. Проверьте свой класс StrVec, использовав его в классах TextQuery и QueryResult (см. раздел 12.3) вместо вектора vector<string>. Упражнение 13.43. Перепишите функцию-член free() так, чтобы для удаления элементов вместо цикла for использовалась функция for_each() и лямбда-выражение (см. раздел 10.3.2). |