Динамическое распределение памяти

Виды памяти

Память, которую использует программа делится на три вида:

1. Статическая память (static memory)

• хранит глобальные переменные и константы;
• размер определяется при компиляции.

2. Стек (stack)

• хранит локальные переменные, аргументы функций и промежуточные значения вычислений;
• размер определяется при запуске программы (обычно выделяется 4 Мб).

3. Куча (heap)

• динамически распределяемая память;
• ОС выделяет память по частям (по мере необходимости).

Динамически распределяемую память следует использовать в случае если мы заранее (на момент написания программы) не знаем сколько памяти нам понадобится (например, размер массива зависит от того, что введет пользователь во время работы программы) и при работе с большими объемами данных (например, массив из 1 000 000 элементов типа int не поместится на стеке).

Работа с динамической памятью в С

Для работы с динамической памятью в языке С используются следующие функции: malloc, calloc, free, realloc. Рассмотрим их подробнее.

void * malloc(size_t size);

В качестве входного параметра функция принимает размер памяти, которую требуется выделить. Возвращаемым значением является указатель на выделенный в куче участок памяти. Для выделения памяти под 1 000 000 элементов типа int необходимо выполнить следующий код:

int * p = malloc(1000000 * sizeof(int));

В языке С++ потребуется небольшая модификация данной кода (из-за того, что в С++ нет неявного приведения указателей):

int * p = (int *) malloc(1000000 * sizeof(int));

Если ОС не смогла выделить память (например, памяти не хватило), то malloc возвращает 0.

После окончания работы с выделенной динамически памятью нужно освободить ее. Для этой цели используется функция free, которая возвращает память под управление ОС.

void free(void * ptr);

В качестве входного параметра в free нужно передать указатель, значение которого получено из функции malloc. Вызов free на указателях полученных не из malloc (например, free(p+10)) приведет к неопределенному поведению. Это связанно с тем, что при выделении памяти при помощи malloc в ячейки перед той, на которую указывает возвращаемый функцией указатель операционная система записывает служебную информацию (см. рис.). При вызове free(p+10) информация находящаяся перед ячейкой (p+10) будет трактоваться как служебная.

void * calloc(size_t nmemb, size_t size);

Функция работает аналогично malloc, но отличается синтаксисом (вместо размера выделяемой памяти нужно задать количество элементов и размер одного элемента) и тем, что выделенная память будет обнулена. Например, после выполнения

int * q = (int *) calloc(1000000, sizeof(int))

q будет указывать на начало массива из миллиона элементов типа int проинициализированных нулями.

void * realloc(void * ptr, size_t size);

Функция изменяет размер выделенной памяти (на которую указывает ptr, полученный из вызова malloc, calloc или realloc). Если размер указанный в параметре size больше, чем тот, который был выделен под указатель ptr, то проверяется, есть ли возможность выделить недостающие ячейки памяти подряд с уже выделенными. Если места недостаточно, то выделяется новый участок памяти размером size и данные по указателю ptr копируются в начало нового участка.

Какие бывают ошибки

1. Потеря памяти

int * p = (int *) malloc(100);
p = (int *) malloc(200); // потерян указатель на первые 100 <code>int</code>'ов, которые теперь нельзя отдать обратно ОС

2. Повторное освобождение выделенной памяти

free(p);
… 
free(p); // неопределенное поведение

Правильно:

free(p);
p = 0;
…
free(p); // отработает без ошибок

Работа с динамической памятью в С++

В С++ есть свой механизм выделения и освобождения памяти — это функции new и delete.

Пример использования new:

int * p = new int[1000000]; // выделение памяти под 1000000 int`ов

Т.е. при использовании функции new не нужно приводить указатель и не нужно использовать sizeof(). Освобождение выделенной при помощи new памяти осуществляется посредством следующего вызова:

delete [] p;

Если требуется выделить память под один элемент, то можно использовать

int * q = new int;

или

int * q = new int(10); // выделенный int проинциализируется значением 10

в этом случае удаление будет выглядеть следующим образом:

delete q;

Замечание:

Выделять динамически небольшие кусочки памяти (например, под один элемент простого типа данных) не целесообразно по двум причинам:

1. При динамическом выделении памяти в ней помимо значения указанного типа будет храниться служебная информация ОС и С/С++. Таким образом потребуется гораздо больше памяти, чем при хранении необходимых данных на стеке.
2. Если в памяти хранить большое количество маленьких кусочков, то она будет сильно фрагментирована и большой массив данных может не поместиться.

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

new позволяет выделять только одномерные массивы, поэтому для работы с многомерными массивами необходимо воспринимать их как массив указателей на другие массивы. Для примера рассмотрим задачу выделения динамической памяти под массив чисел размера n на m.

1ый способ

На первом шаге выделяется указатель на массив указателей, а на втором шаге, в цикле каждому указателю из массива выделяется массив чисел в памяти:

int ** a = new int*[n];
for (int i = 0; i != n; ++i)
  a[i] = new int[m];

Однако, этот способ плох тем, что в нём требуется n+1 выделение памяти, а это достаточно дорогая по времени операция.

2ой способ

На первом шаге выделение массива указателей и массива чисел размером n на m. На втором шаге каждому указателю из массива ставится в соответствие строка в массиве чисел.

int ** a = new int*[n];
a[0] = new int[n*m];
for (int i = 1; i != n; ++i)
  a[i] = a[0] + i*m;

В данном случае требуется всего 2 выделения памяти. Для освобождения памяти потребуется выполнить:

1ый способ:

for (int i = 0; i != n; ++i)
  delete [] a[i];
delete [] a;

2ой способ:

delete [] a[0];
delete [] a;

Таким образом, второй способ опять же требует гораздо меньше вызовов функции delete [], чем первый.