# Глава 15.5. Динамическое выделение памяти для массивов Если сишный массив создан глобально или помечен как `static`, то располагается в статической области памяти. В остальных случаях такой массив живёт в автоматической памяти. Поэтому у него константная длина: нужно знать заранее, сколько статической или автоматической памяти нужно резервировать. Но есть способ превратить сишный массив в динамический и создать его на куче. ## Выражения new[] и delete[] для массивов Для того, чтобы создать массив на куче, используются версии операторов с квадратными скобками [new[]](https://en.cppreference.com/w/cpp/memory/new/operator_new.html) и [delete[]](https://en.cppreference.com/w/cpp/memory/new/operator_delete.html). Если аллоцировать массив в динамической памяти, требование к константности длины пропадает. Так выглядит создание неинициализированного массива и его уничтожение: ```cpp {.example_for_playground .example_for_playground_009} int n = 5; int * arr = new int[n]; // ... Заполняем массив, работаем с ним delete[] arr; ``` Квадратные скобки `delete[]` всегда пусты. В квадратные скобки выражения `new T[n]` может быть передано любое целое неотрицательное число. Оно не обязано быть константой. Допустимо выделение массива нулевого размера: `new T[0]`. Но раз такой массив не содержит элементов, разыменовывать на него указатель запрещено. Такая на первый взгляд странная возможность может пригодиться в ряде случаев. Например, чтобы не писать лишних проверок: ```cpp if (n > 0) arr = new T[n]; else arr = nullptr; ``` Во-вторых, в отличие от нулевого указателя, такой массив имеет корректный адрес, и его можно передавать в алгоритмы стандартной библиотеки. Возможность создавать динамические массивы нулевой длины отличает их от статических массивов. При попытке завести обычный сишный массив нулевой длины компилятор вернёт ошибку. Чтобы инициализировать массив, в фигурных скобках перечисляются значения элементов: ```cpp double * arr = new double[3]{1.0, 2.2, 7.8}; delete[] arr; ``` ## Ещё раз про принцип парности Повторение — мать учения. Особенно в таком важном вопросе, как работа с памятью. Операции для выделения и освобождения памяти — парные. Вызов `new T` неотделим от `delete`, а `new T[n]` — от `delete[]`. Смешивать `new T` и `delete[]` либо `new T[n]` и `delete` **нельзя**. Это UB. ## Работа с динамической памятью на примере вектора Теперь у нас есть всё необходимое, чтобы написать свою реализацию вектора целых чисел. Она будет примитивной, но работоспособной. Сначала опишем интерфейс класса. А потом добавим реализацию методов. ```cpp class Vector { public: Vector() = default; // Создаёт вектор из n элементов со значением val Vector(std::size_t n, int val); ~Vector(); // Возвращает количество элементов std::size_t size(); // Возвращает ёмкость - под сколько элементов // выделена память std::size_t capacity(); // Возвращает элемент по индексу. Если индекс за // пределами вектора, кидает исключение int & at(std::size_t i); // Возвращает элемент по индексу int & operator[](std::size_t i); // Увеличивает ёмкость вектора: выделяет под него // память бОльшего размера. Если значение capacity // меньше текущей ёмкости, то ничего не делает void reserve(std::size_t capacity); // Изменяет реальный размер вектора. Если новый размер // меньше текущего, удаляет элементы с конца. Если // больше, то добавляет элементы, инициализированные // значением по умолчанию. Если размеры равны, то // ничего не делает void resize(std::size_t size); // Добавляет элемент в конец void push_back(int val); // Удаляет последний элемент void pop_back(); private: // Указатель на сишный массив, в котором // хранятся элементы int * m_elements = nullptr; // Реальное количество элементов std::size_t m_size = 0; // Ёмкость: под сколько элементов выделена память std::size_t m_capacity = 0; }; ``` Обратите внимание на метод `int & operator[](std::size_t i)`: он нужен для обращения к объекту `Vector` через оператор взятия по индексу `[]`. Подробнее про операторы будет в следующих главах. Важная ремарка: чтобы избежать потенциальных утечек памяти при работе с классом, в нём нужно запретить конструкторы и операторы копирования и перемещения. Сейчас мы этого делать не будем. Что это такое и зачем оно нужно, мы разберём в главах про классы. Поведение методов класса `Vector` приблизим к поведению [аналогичных методов](https://en.cppreference.com/w/cpp/container/vector.html) `std::vector`. Чтобы посмотреть полный код класса `Vector`, откройте этот пример в песочнице. Дальше мы будем последовательно разбирать его методы. ```cpp {.example_for_playground .example_for_playground_002} Vector v(4, 2); v.reserve(15); v.push_back(3); for(std::size_t i = 0; i < v.size(); ++i) std::println("{}", v[i]); ``` Изобразим, как объект `Vector v(3, 1)` расположен в памяти. ``` Автоматическая память (стек) Динамическая память (куча) ┌─────────────────────────┐ ┌───────────────────────────┐ │ Объект Vector │ │ Массив int │ │ ┌─────────────────────┐ │ │ ┌───┬───┬───┬───┬───┬───┐ │ │ │ m_elements = 0x.... ├─┼───────>│ │ 1 │ 1 │ 1 │ 1 │ ? │ ? │ │ │ ├─────────────────────┤ │ │ └───┴───┴───┴───┴───┴───┘ │ │ │ m_size = 3 │ │ │ ╰─────────────╯ │ │ ├─────────────────────┤ │ │ Размер │ │ │ m_capacity = 5 │ │ │ │ │ └─────────────────────┘ │ │ ╰──────────────────────╯ │ └─────────────────────────┘ │ Ёмкость │ └───────────────────────────┘ ``` Поля объекта последовательно расположены в автоматической памяти. И одно из них ссылается на массив в динамической памяти. Начнём реализовывать методы `Vector`. Заведём перегрузку конструктора для инициализации вектора `n` элементами, равными `val`. ```cpp Vector::Vector(std::size_t n, int val): m_elements{new int[n]}, m_size{n}, m_capacity{n} { for (std::size_t i = 0; i < m_size; ++i) m_elements[i] = val; } ``` Выражение `new int[n]` выделяет память под сишный массив. Указатель на эту память инициализирует поле `m_elements` в [списке инициализации полей.](/courses/cpp/chapters/cpp_chapter_0122/#block-member-initializer-list) Улучшите эту реализацию конструктора: {.task_text} - Для присваивания элементам значений вместо цикла используйте алгоритм [std::fill()](https://en.cppreference.com/w/cpp/algorithm/fill.html). - Выделяйте и заполняйте массив не в теле конструктора, а в списке инициализации. Инициализация всех полей в списке инициализации конструктора — очень хорошая практика. Тело конструктора при этом остаётся пустым. - Для этого напишите вспомогательную функцию `make_array()`, которая аллоцирует массив из `n` элементов, заполняет его с помощью `std::fill()` и возвращает на него указатель. ```cpp {.task_source #cpp_chapter_0155_task_0040} int * make_array(std::size_t n, int val) { } Vector::Vector(std::size_t n, int val) { } ``` В списке инициализации присвойте указателю `m_elements` значение, которое возвращает функция `make_array()`. {.task_hint} ```cpp {.task_answer} int * make_array(std::size_t n, int val) { int * elements{new int[n]}; std::fill(elements, elements + n, val); return elements; } Vector::Vector(std::size_t n, int val): m_elements{make_array(n, val)}, m_size{n}, m_capacity{n} { } ``` Конструктор готов. Пример его вызова для создания вектора из 5 элементов со значением 9: ```cpp Vector v(5, 9); ``` Сразу же определим деструктор: ```cpp Vector::~Vector() { delete[] m_elements; } ``` Методы `size()` и `capacity()` просто возвращают значения соответствующих полей: ```cpp std::size_t Vector::size() { return m_size; } std::size_t Vector::capacity() { return m_capacity; } ``` Метод `at()` принимает индекс элемента и возвращает на него ссылку. Если индекс выходит за границы массива, будет брошено исключение: ```cpp int & Vector::at(std::size_t i) { if (i >= m_size) { throw std::out_of_range( std::format("Index {} is out of bounds. Vector size: {}", i, m_size)); } return m_elements[i]; } ``` Есть ли в этом коде утечка памяти? ```cpp {.example_for_playground .example_for_playground_010} int main() { Vector numbers(4, 100); try { std::println("{}", numbers.at(5)); } catch(const std::out_of_range & e) { std::println("Couldn't get element from vector: {}", e.what()); } } ``` Мы завели вектор из 4-х элементов и обратились по индексу 5. Метод `at()` бросает исключение. Оно перехватывается в блоке `catch` и начинается **раскрутка стека** (stack unwinding). - Со стека удаляются фреймы всех функций до той, которая обрабатывает исключение. - При снятии фрейма со стека происходит автоматическое удаление переменных из этого фрейма. Вызываются их деструкторы. - Выполнение кода внутри блока `try` прерывается и управление передаётся блоку `catch`. Для локальных переменных блока `try` вызываются деструкторы. Это означает, что для объекта `numbers` будет вызван деструктор. Значит, утечки памяти нет. Вы можете открыть пример кода в песочнице и удостовериться в этом. Как насчёт утечки в таком коде? ```cpp {.example_for_playground .example_for_playground_011} int main() { Vector numbers(4, 100); std::println("{}", numbers.at(5)); } ``` Брошенное исключение перехватывать некому. Произойдёт ли в таком случае раскрутка стека и соответственно будет ли вызван деструктор `Vector`, зависит от компилятора. Соответственно, в этом коде есть потенциальная утечка. Правда она чисто формальная, потому что не обработанное исключение приводит к завершению программы. В этот момент отданная процессу память возвращается операционной системе. Реализация оператора `[]` даже проще метода `at()`: ```cpp int & Vector::operator[](std::size_t i) { return m_elements[i]; } ``` Метод `reserve()` увеличивает ёмкость вектора: выделяет под него память нового размера. Если новый размер меньше текущей ёмкости, то метод ничего не делает. ```cpp void Vector::reserve(std::size_t new_capacity) { if (new_capacity <= m_capacity) return; int * new_elements = new int[new_capacity]; // Копирование for (std::size_t i = 0; i < m_size; ++i) new_elements[i] = m_elements[i]; // Обмен указателей int * tmp = new_elements; new_elements = m_elements; m_elements = tmp; delete[] new_elements; m_capacity = new_capacity; } ``` Что происходит в этом методе? Фактически мы переместили массив из одной области памяти в другую. Это называется **реаллокацией.** Здесь: - Создан новый массив `new_elements` подходящего размера. - В него скопированы элементы из старого массива. - Обновлено значение указателя `m_elements`, чтобы он ссылался на новую область памяти. - Освобождена ненужная область памяти. Важно, что _за_ последним скопированным элементом в новом массиве хранится произвольный мусор. Чтобы вместо мусора получить значения по умолчанию, вместо `reserve()` нужно вызывать метод `resize()`, про который речь пойдёт дальше. Улучшите метод `reserve()`: {.task_text} - Замените цикл с поэлементным копированием элементов на алгоритм [std::copy()](https://en.cppreference.com/w/cpp/algorithm/copy.html). - Замените обмен указателей через временную переменную на вызов [std::swap()](https://en.cppreference.com/w/cpp/utility/swap.html). ```cpp {.task_source #cpp_chapter_0155_task_0050} void Vector::reserve(std::size_t new_capacity) { } ``` Копирование элементов с помощью алгоритма: `std::copy(m_elements, m_elements + m_size, new_elements)`. {.task_hint} ```cpp {.task_answer} void Vector::reserve(std::size_t new_capacity) { if (new_capacity <= m_capacity) return; int * new_elements = new int[new_capacity]; std::copy(m_elements, m_elements + m_size, new_elements); std::swap(m_elements, new_elements); delete[] new_elements; m_capacity = new_capacity; } ``` Перейдём к реализации метода `resize()`. ```cpp void Vector::resize(std::size_t size) { if (size <= m_size) { m_size = size; return; } reserve(size); std::fill(m_elements + m_size, m_elements + size, int{}); m_size = size; } ``` Теперь напишем метод для добавления элемента в конец вектора. При исчерпании ёмкости будем её удваивать. ```cpp void Vector::push_back(int val) { if (m_size + 1 > m_capacity) reserve(std::max(m_capacity, 1uz) * 2); m_elements[m_size++] = val; } ``` Удвоение объёма массива — далеко не единственная стратегия роста. Например, чтобы сократить расход памяти, на больших размерах массива можно перейти от x2 к увеличению на небольшой процент. Обратите внимание на использование [постфиксной формы](/courses/cpp/chapters/cpp_chapter_0022/#block-post-increment) инкремента `m_size++`, которая сначала возвращает значение, а потом увеличивает его. Поэтому в выражении `m_elements[m_size++]` нет выхода за границы массива. Итак, мы написали простой прототип класса вектора с минимальным набором методов. Для этого использовали указатель на массив и два числа: реальный размер вектора `size` и его вместимость `capacity`. Интересный факт: большинство стандартных реализаций `std::vector` вместо одного указателя и двух чисел задействуют три указателя: на начало массива, на последний элемент и на конец выделенной под массив памяти. Такой подход эффективен при вставке и удалении с конца. ## Работа с динамической памятью на примере двусвязного списка В главе про основы работы с указателями вы уже успели порешать задачи, связанные [со структурой](/courses/cpp/chapters/cpp_chapter_0152/#block-listnode) `ListNode`. Она реализует узел односвязного списка: ```cpp struct ListNode { ListNode() {} explicit ListNode(int value) : val(value) {} explicit ListNode(int value, ListNode * next_node) : val(value), next(next_node) {} int val = 0; ListNode * next = nullptr; }; ``` А теперь представьте класс односвязного списка, состоящий из узлов `ListNode`: ```cpp class List { public: List() = default; ~List(); // Возвращает длину списка std::size_t len(); // Добавляет новый узел со значением val в начало void push_front(int val); // Ищет элемент со значением val, удаляет его и возвращает true. // Если такой элемент не найден, ничего не делает и возвращает false bool remove(int val); // Возвращает элемент по индексу. Если индекс за пределами // списка, возвращает nullptr ListNode * get(std::size_t index); private: // Указатель на первый элемент списка ListNode * head = nullptr; // Длина списка std::size_t size = 0; }; ``` Реализуйте методы класса `List`. {.task_text} ```cpp {.task_source #cpp_chapter_0155_task_0060} List::~List() { } std::size_t List::len() { } void List::push_front(int val) { } bool List::remove(int val) { } ListNode * List::get(std::size_t index) { } ``` Чтобы написать деструктор, нужно понять, как в цикле удалить все узлы списка. Для этого пока `head != nullptr` делайте следующее: заводите временный указатель `ListNode * tmp = head`. Затем сдвигайте голову списка: `head = head->next`. И наконец освобождайте память по временному указателю: `delete tmp`. Он указывает на голову списка. {.task_hint} ```cpp {.task_answer} List::~List() { while (head != nullptr) { ListNode * tmp = head; head = head->next; delete tmp; } } std::size_t List::len() { return size; } void List::push_front(int val) { ListNode * new_head = new ListNode{val}; new_head->next = head; head = new_head; ++size; } bool List::remove(int val) { if (head == nullptr) return false; if (head->val == val) { ListNode* tmp = head; head = head->next; delete tmp; --size; return true; } ListNode * cur = head; while (cur->next != nullptr && cur->next->val != val) cur = cur->next; if (cur->next) { ListNode * tmp = cur->next; cur->next = cur->next->next; delete tmp; --size; return true; } return false; } ListNode * List::get(std::size_t index) { ListNode * cur = head; std::size_t i = 0; while (cur != nullptr) { if (i == index) return cur; cur = cur->next; ++i; } return nullptr; } ``` ---------- ## Резюме - Чтобы аллоцировать память под массив, используются версии операторов `new T[n]` и `delete[]`. - Будьте бдительны: выделенную под массив память нужно освободить именно вызовом `delete[]`, а не `delete`. - Справедливо и обратное: нельзя освободить память под единственную переменную вызовом `delete[]`. - Допустимо выделение памяти под пустой массив: `new T[0]`. Но разыменование указателя на него — это UB.