Динамическое распределение памяти
Память, которую использует программа делится на три вида:
- Статическая память (static memory)
- хранит глобальные переменные и константы;
- размер определяется при компиляции.
- Стек (stack)
- хранит локальные переменные, аргументы функций и промежуточные значения
вычислений;
- размер определяется при запуске программы (обычно выделяется 4 Мб).
- Куча (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 int`ов, которые теперь нельзя отдать обратно ОС
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;
Замечание:
Выделять динамически небольшие кусочки памяти (например, под один элемент простого типа данных) не целесообразно по двум причинам:
- При динамическом выделении памяти в ней помимо значения указанного типа будет храниться служебная информация ОС и С/С++. Таким образом потребуется гораздо больше памяти, чем при хранении необходимых данных на стеке.
- Если в памяти хранить большое количество маленьких кусочков, то она будет сильно фрагментирована и большой массив данных может не поместиться.
Многомерные массивы.
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 [], чем первый.