Динамическая память и многомерные массивы

This lesson is not translated yet – the Russian original is below.

Стек удобен, но у него два ограничения: размер объекта должен быть известен на компиляции, и объект не может пережить свою функцию. Всё, что не укладывается в эти рамки, живёт в куче – и отвечаете за него вы.

new и delete

int* p = new int;          // один int, значение не определено
int* q = new int(42);      // один int со значением 42
int* a = new int[100];     // массив на 100 int

delete p;
delete q;
delete[] a;                // для массива – только эта форма

new делает две вещи: просит у аллокатора блок нужного размера и вызывает конструктор (для встроенных типов – ничего не делает или инициализирует значением). delete – в обратном порядке: вызывает деструктор и возвращает блок аллокатору.

Размер массива, в отличие от стека, может быть вычислен во время работы:

size_t n = 0;
std::cin >> n;

int* data = new int[n];    // здесь это законно
delete[] data;

Формы обязаны совпадать: new ↔ delete, new[] ↔ delete[]. Перепутать – неопределённое поведение, а не «немного утечёт»: аллокатор хранит количество элементов служебным полем рядом с блоком, и скалярная форма его не читает. Мешать new с malloc/free нельзя тем более – это два независимых аллокатора.

Три способа выстрелить себе в ногу

Утечка – потеряли последний указатель на выделенный блок:

void Leak() {
    int* p = new int[1000];
    if (SomethingWrong()) {
        return;             // блок остался, указателя больше нет
    }
    delete[] p;
}

Ранний return – самый частый вид утечки. Исключение, брошенное между new и delete, даёт ровно тот же эффект.

Висячий указатель – память освободили, указатель остался:

int* p = new int(42);
delete p;
std::cout << *p;            // читаем чужую память

Двойное освобождение – delete по одному адресу дважды. Портит внутренние структуры аллокатора; падение обычно происходит позже и в другом месте.

int* p = new int(42);
delete p;
p = nullptr;                // дешёвая страховка: delete от nullptr ничего не делает
delete p;                   // теперь безопасно

Владение

Указатель не говорит ничего о том, кто обязан вызвать delete. Это соглашение между людьми, и записывать его надо явно – хотя бы в комментарии, а лучше в типе.

Widget* Create();               // кто удаляет? Из сигнатуры не видно
void Register(Widget* w);       // забрал себе или только посмотрел?

Ответ C++ на эту проблему – владеющий объект: класс, который держит указатель и освобождает его в деструкторе. Тогда компилятор сам расставляет delete на всех выходах из функции, включая исключения. Этот приём называется RAII, к нему мы придём в модуле про классы, а готовые владеющие обёртки – unique_ptr и shared_ptr – разберём в модуле про дополнительные возможности.

В современном C++ голые new и delete в прикладном коде почти не встречаются: массив переменной длины – это std::vector, единственный владелец – std::unique_ptr. Уметь работать руками нужно, чтобы понимать, что происходит внутри этих типов и как читать чужой код возрастом старше десяти лет.

Многомерные массивы на стеке

int a[3][4];                                     // 3 строки по 4 элемента
int b[][3] = { {1, 2, 3}, {4, 5, 6} };           // внешнюю размерность выведет компилятор

Ключевой факт: такой массив лежит в памяти одним непрерывным куском. Сначала все элементы нулевой строки, затем первой, и так далее. Никакой таблицы указателей на строки нет.

Отсюда следует, что инициализировать его можно и плоским списком – это ровно та же память:

int a[][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };      // тот же массив 3 × 3

И что индексация – это арифметика:

a[i][j];                       // компилятор превращает это в
*((int*)a + i * 3 + j);        // вот такое обращение

Многомерные массивы в куче

Здесь картина другая. Прямого аналога new int[n][m] с двумя переменными размерами нет, и делают обычно одно из двух.

Массив указателей на строки. Гибко, но память фрагментирована, и освобождать нужно в два приёма:

int** matrix = new int*[rows];
for (size_t i = 0; i < rows; ++i) {
    matrix[i] = new int[cols];
}

matrix[1][2] = 7;

for (size_t i = 0; i < rows; ++i) {
    delete[] matrix[i];
}
delete[] matrix;               // порядок обратный выделению

Один плоский блок с ручной индексацией. Одно выделение, одно освобождение, данные лежат подряд – процессорному кэшу это нравится гораздо больше:

int* matrix = new int[rows * cols];

matrix[1 * cols + 2] = 7;      // вместо matrix[1][2]

delete[] matrix;

Разница не косметическая. Проход по плоскому блоку читает память последовательно, и предвыборка процессора работает; проход по массиву указателей прыгает по куче. На больших матрицах разрыв бывает кратным. Именно поэтому библиотеки линейной алгебры хранят матрицы плоско и передают stride отдельным параметром.

Кстати, о перестановке строк: в варианте с указателями поменять две строки местами – это обмен двух указателей, независимо от длины строки. В плоском варианте придётся копировать элементы. Выбор структуры данных всегда что-то делает дешевле, а что-то дороже.