Как освобождается память выделенная для динамического массива
Для работы с динамической памятью в языке С используются следующие функции: 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 памяти осуществляется посредством следующего вызова:
Если требуется выделить память под один элемент, то можно использовать
int * q = new int;
int * q = new int(10); // выделенный int проинциализируется значением 10
в этом случае удаление будет выглядеть следующим образом:
- При динамическом выделении памяти в ней помимо значения указанного типа будет храниться служебная информация ОС и С/С++. Таким образом потребуется гораздо больше памяти, чем при хранении необходимых данных на стеке.
- Если в памяти хранить большое количество маленьких кусочков, то она будет сильно фрагментирована и большой массив данных может не поместиться.
Многомерные массивы.
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 выделения памяти.
Для освобождения памяти требуется выполнить:
for (int i = 0; i != n; ++i)
delete [] a[i];
delete [] a;
delete [] a[0];
delete [] a;
Таким образом, второй способ опять же требует гораздо меньше вызовов функции delete [], чем первый.
Динамическая память
При создании массива с фиксированными размерами под него выделяется определенная память. Например, пусть у нас будет массив с пятью элементами:
double numbers[5] = ;
Для такого массива выделяется память 5 * 8 (размер типа double) = 40 байт. Таким образом, мы точно знаем, сколько в массиве элементов и сколько он занимает памяти. Однако это не всегда удобно. Иногда бывает необходимо, чтобы количество элементов и соответственно размер выделяемой памяти для массива определялись динамически в зависимости от некоторых условий. Например, пользователь сам может вводить размер массива. И в этом случае для создания массива мы можем использовать динамическое выделение памяти.
Для управления динамическим выделением памяти используется ряд функций, которые определены в заголовочном файле stdlib.h :
-
malloc() . Имеет прототип
void *malloc(unsigned s);
void *calloc(unsigned n, unsigned m);
void *realloc(void *bl, unsigned ns);
void *free(void *bl);
malloc
Функция malloc() выделяет память длиной для определенного количества байт и возвращает указатель на начало выделенной памяти. Через полученный указатель мы можем помещать данные в выделенную память. Рассмотрим простой пример:
#include #include // для подключения функции malloc int main(void) < int *ptr = malloc(sizeof(int)); // выделяем память для одного int *ptr = 24; // помещаем значение в выделенную память printf("%d \n", *ptr); free(ptr); >
Здесь с помощью функции malloc выделяется память для одного объекта int . Чтобы узнать, сколько байтов надо выделить, передаем в функцию malloc размер типа int на текущей и в результате получаем указатель ptr , который указывает на выделенную память
int *ptr = malloc(sizeof(int));
То есть поскольку int на большинстве архитектур занимает 4 байта, то в большинстве случаев будет выделяться память объемом в 4 байта. Стоит отметить, что мы также могли бы получить размер через разыменование указателя:
int *ptr = malloc(sizeof *ptr);
Для универсальности возвращаемого значения в качестве результата функция malloc() (как и calloc() и realloc() ) возвращает указатель типа void * . Но в нашем случае создается массив типа int, для управления которым используется указатель типа int * , поэтому выполняется неявное приведение результата функции malloc к типу int * .
Далее через этот указатель с помощью операции разыменования помещаем в выделенный участок памяти число 24:
*ptr = 24;
В дальнейшем, используя указатель, можно получить значение из выделенного участка памяти:
printf("%d \n", *ptr);
После завершения работы освобождаем память, передавая указатель в функцию free() :
free(ptr);
Стоит отметить, что теоретически мы можем столкнуться с тем, что функции malloc() не удастся выделить требуемую память, и тогда она возвратит NULL. Чтобы избежать подобной ситуации перед использованием указателя мы можем проверять его на значение NULL:
#include #include // для подключения функции malloc int main(void) < int *ptr = malloc(sizeof(int)); // выделяем память для одного int if(ptr != NULL) < *ptr = 24; // помещаем значение в выделенную память printf("%d \n", *ptr); >free(ptr); >
Немотря на освобождение памяти с помощью функции free() указатель сохраняет свой адрес, и теоретически мы можем обращаться к памяти по данному указателю. Однако полученные значения уже будут неопределенными и недетеминированными. Поэтому некоторые советуют после освобождения памяти также устанавливать для указателя значение NULL :
free(ptr); ptr = NULL;
Выделение памяти для массива
Подобным образом можно выделять память и под набор объектов. Например, выделим память для массива из 4-х чисел int:
#include #include int main(void) < int n = 4; int *ptr = malloc(n * sizeof(int)); // выделяем память для 4-х чисел int if(ptr) < // помещаем значения в выделенную память ptr[0] = 1; ptr[1] = 2; ptr[2] = 3; ptr[3] = 5; // получаем значения for(int i = 0; i < n; i++) < printf("%d", ptr[i]); >> free(ptr); >
Выделение памяти для структуры
Аналогичным образом можно выделять память для одной или набора структур:
#include #include struct person < char* name; int age; >; int main(void) < // выделяем память для одной структуры person struct person *ptr = malloc(sizeof(struct person)); if(ptr) < // помещаем значения в выделенную память ptr->name = "Tom"; ptr->age = 38; // получаем значения printf("%s : %d", ptr->name, ptr->age); // Tom : 38 > free(ptr); return 0; >
calloc
Функция calloc() имеет прототип
void *calloc(unsigned n, unsigned m);
Она выделяет память для n элементов по m байт каждый и возвращает указатель на начало выделенной памяти. В случае неудачного выполнения возвращает NULL
В отличие от функции malloc() она инициализирует все выделенные байты памяти нулями. Например, выделим память для одного объекта int :
#include #include int main(void) < // выделяем память для одного объекта int int *ptr = calloc(1, sizeof(int)); if(ptr) < // получаем значение по умолчанию - 0 printf("Initial value: %d", *ptr); // Initial value: 0 // устанавливаем новое значение *ptr = 15; // получаем новое значение printf("New value: %d", *ptr); // New value: 15 >free(ptr); return 0; >
Initial value: 0 New value: 15
Подобным образом можно выделить память и для других объектов. Например, выделим память для массива из 4-х объектов int :
#include #include int main(void) < // выделяем память для 4-х объектов int int n = 4; int *ptr = calloc(n, sizeof(int)); if(ptr) < // устанавливаем значения ptr[0] = 1; ptr[1] = 2; ptr[2] = 3; ptr[3] = 5; // получаем значения for(int i = 0; i < n; i++) < printf("%d", ptr[i]); >> free(ptr); >
realloc
Функция realloc() позволяет изменить размер памяти, ранее выделенной с помощью функций malloc() b calloc() . Имеет прототип
void *realloc(void *bl, unsigned ns);
Первый параметр представляет указатель на ранее выделенный блок памяти. А второй параметр представляет новый размер блока памяти в байтах.
Если указатель bl имеет значение NULL , то есть память не выделялась, то действие функции аналогично действию malloc
Рассмотрим небольшой пример:
#include #include int main(void) < // выделяем память для 1-го объекта int int size = sizeof(int); int *ptr = malloc(size); if(ptr) < // отображаем адрес и размер памяти printf("Addresss: %p \t Size: %d\n", (void*)ptr, size); >// расширяем память до размера 4-х объектов int size = 4 * sizeof(int); int *ptr_new = realloc(ptr, size); // если выделение памяти прошло успещно if(ptr_new) < printf("Reallocation\n"); // заново отображаем адрес и размер памяти printf("Addresss: %p \t Size: %d\n", (void*)ptr_new, size); free(ptr_new); // освобождаем новый указатель >else < free(ptr); // освобождаем старый указатель >>
Здесь сначала выделяем память для одного объекта int с помощью функции malloc.
int size = sizeof(int); int *ptr = malloc(size);
Если память успешно выделена, то выводим на консоль адрес и размер выделенного блока памяти. Затем с помощью функции realloc расширяем память до 4 объектов int
size = 4 * sizeof(int); int *ptr_new = realloc(ptr, size);
Если увеличение памяти прошло успешно, то заново выводим данные на консоль и освобождаем память по новому указателю. Если увеличение памяти прошло не удачно, то освобождаем память но старому указателю.
Консольный вывод в моем случае
Addresss: 0000018B078A82F0 Allocated: 4 Reallocation Addresss: 0000018B078A82F0 Allocated: 16
Стоит отметить, что нам необязательно создавать новый указатель, мы можем присвоить значение старому указателю:
#include #include int main(void) < int size = sizeof(int); int *ptr = malloc(size); if(ptr) < printf("Addresss: %p \t Allocated: %d\n", (void*)ptr, size); >size = 4 * sizeof(int); ptr = realloc(ptr, size); // используем старый указатель if(ptr) < printf("Reallocation\n"); printf("Addresss: %p \t Allocated: %d\n", (void*)ptr, size); >free(ptr); >
Динамическое выделение памяти
Теги: Си память, malloc, calloc, realloc, free, Ошибки выделения памяти, Висячие указатели, Динамические массивы, Многомерные динамические массивы.
- Функция malloc
- Освобождение памяти с помощью free
- Работа с двумерными и многомерными массивами
- Функция calloc
- Функция realloc
- Типичные ошибки при динамической работе с памятью
- Различные аргументы realloc и malloc
malloc
В предыдущей главе уже обсуждалось, что локальные переменные кладутся на стек и существую до тех пор, пока мы не вышли из функции. С одной стороны, это позволяет автоматически очищать память, с другой стороны, существует необходимость в переменных, время жизни которых мы можем контролировать самостоятельно. Кроме того, нам необходимо динамическое выделение памяти, когда размер используемого пространства заранее не известен. Для этого используется выделение памяти на куче. Недостатков у такого подхода два: во-первых, память необходимо вручную очищать, во-вторых, выдеение памяти – достаточно дорогостоящая операция.
Для выделения памяти на куче в си используется функция malloc (memory allocation) из библиотеки stdlib.h
void * malloc(size_t size);
Функция выделяет size байтов памяти и возвращает указатель на неё. Если память выделить не удалось, то функция возвращает NULL. Так как malloc возвращает указатель типа void, то его необходимо явно приводить к нужному нам типу. Например, создадим указатель, после этого выделим память размером в 100 байт.
#include #include #include void main()
После того, как мы поработали с памятью, необходимо освободить память функцией free.
Используя указатель, можно работать с выделенной памятью как с массивом. Пример: пользователь вводит число – размер массива, создаём массив этого размера и заполняем его квадратами чисел по порядку. После этого выводим и удаляем массив.
#include #include #include void main() < const int maxNumber = 100; int *p = NULL; unsigned i, size; do < printf("Enter number from 0 to %d: ", maxNumber); scanf("%d", &size); if (size < maxNumber) < break; >> while (1); p = (int*) malloc(size * sizeof(int)); for (i = 0; i < size; i++) < p[i] = i*i; >for (i = 0; i < size; i++) < printf("%d ", p[i]); >_getch(); free(p); >
p = (int*) malloc(size * sizeof(int));
Здесь (int *) – приведение типов. Пишем такой же тип, как и у указателя.
size * sizeof(int) – сколько байт выделить. sizeof(int) – размер одного элемента массива.
После этого работаем с указателем точно также, как и с массивом. В конце не забываем удалять выделенную память.
Теперь представим на рисунке, что у нас происходило. Пусть мы ввели число 5.
Функция malloc выделила память на куче по определённому адресу, после чего вернула его. Теперь указатель p хранит этот адрес и может им пользоваться для работы. В принципе, он может пользоваться и любым другим адресом.
Когда функция malloc «выделяет память», то она резервирует место на куче и возвращает адрес этого участка. У нас будет гарантия, что компьютер не отдаст нашу память кому-то ещё. Когда мы вызываем функцию free, то мы освобождаем память, то есть говорим компьютеру, что эта память может быть использована кем-то другим. Он может использовать нашу память, а может и нет, но теперь у нас уже нет гарантии, что эта память наша. При этом сама переменная не зануляется, она продолжает хранить адрес, которым ранее пользовалась.
Это очень похоже на съём номера в отеле. Мы получаем дубликат ключа от номера, живём в нём, а потом сдаём комнату обратно. Но дубликат ключа у нас остаётся. Всегда можно зайти в этот номер, но в нём уже кто-то может жить. Так что наша обязанность – удалить дубликат.
Иногда думают, что происходит «создание» или «удаление» памяти. На самом деле происходит только перераспределение ресурсов.
Освобождение памяти с помощью free
Т еперь рассмотри, как происходит освобождение памяти. Переменная указатель хранит адрес области памяти, начиная с которого она может им пользоваться. Однако, она не хранит размера этой области. Откуда тогда функция free знает, сколько памяти необходимо освободить?
- 1. Можно создать карту, в которой будет храниться размер выделенного участка. Каждый раз при освобождении памяти компьютер будет обращаться к этим данным и получать нужную информацию.
- 2. Второе решение более распространено. Информация о размере хранится на куче до самих данных. Таким образом, при выделении памяти резервируется места больше и туда записывается информация о выделенном участке. При освобождении памяти функция free «подсматривает», сколько памяти необходимо удалить.
Работа с двумерными и многомерными массивами
Д ля динамического создания двумерного массива сначала необходимо создать массив указателей, после чего каждому из элементов этого массива присвоить адрес нового массива.
Для удаления массива необходимо повторить операцию в обратном порядке — удалить сначала подмассивы, а потом и сам массив указателей.
#include #include #include #define COL_NUM 10 #define ROW_NUM 10 void main() < float **p = NULL; unsigned i; p = (float**) malloc(ROW_NUM * sizeof(float*)); for (i = 0; i < ROW_NUM; i++) < p[i] = (float*) malloc(COL_NUM * sizeof(float)); >//Здесь какой-то важный код for (i = 0; i < ROW_NUM; i++) < free(p[i]); >free(p); >
- 1. Создавать массивы «неправильной формы», то есть массив строк, каждая из которых имеет свой размер.
- 2. Работать по отдельности с каждой строкой массива: освобождать память или изменять размер строки.
Создадим «треугольный» массив и заполним его значениями
#include #include #include #define SIZE 10 void main() < int **A; int i, j; A = (int**) malloc(SIZE * sizeof(int*)); for (i = 0; i < SIZE; i++) < A[i] = (int*) malloc((i + 1) * sizeof(int)); >for (i = 0; i < SIZE; i++) < for (j = i; j >0; j--) < A[i][j] = i * j; >> for (i = 0; i < SIZE; i++) < for (j = i; j >0; j--) < printf("%d ", A[i][j]); >printf("\n"); > for (i = SIZE-1; i > 0; i--) < free(A[i]); >free(A); _getch(); >
Чтобы создать трёхмерный массив, по аналогии, необходимо сначала определить указатель на указатель на указатель, после чего выделить память под массив указателей на указатель, после чего проинициализировать каждый из массивов и т.д.
calloc
Ф ункция calloc выделяет n объектов размером m и заполняет их нулями. Обычно она используется для выделения памяти под массивы. Синтаксис
void* calloc(size_t num, size_t size);
realloc
Е щё одна важная функция – realloc (re-allocation). Она позволяет изменить размер ранее выделенной памяти и получает в качестве аргументов старый указатель и новый размер памяти в байтах:
void* realloc(void* ptr, size_t size)
Функция realloc может как использовать ранее выделенный участок памяти, так и новый. При этом не важно, меньше или больше новый размер – менеджер памяти сам решает, где выделять память.
Пример – пользователь вводит слова. Для начала выделяем под слова массив размером 10. Если пользователь ввёл больше слов, то изменяем его размер, чтобы хватило места. Когда пользователь вводит слово end, прекращаем ввод и выводим на печать все слова.
#include #include #include #include #define TERM_WORD "end" #define SIZE_INCREMENT 10 void main() < //Массив указателей на слова char **words; //Строка, которая используется для считывания введённого пользователем слова char buffer[128]; //Счётчик слов unsigned wordCounter = 0; //Длина введённого слова unsigned length; //Размер массива слов. Для уменьшения издержек на выделение памяти //каждый раз будем увеличивать массив слов не на одно значение, а на //SIZE_INCREMENT слов unsigned size = SIZE_INCREMENT; int i; //Выделяем память под массив из size указателей words = (char**) malloc(size*sizeof(char*)); do < printf("%d: ", wordCounter); scanf("%127s", buffer); //Функция strcmp возвращает 0, если две строки равны if (strcmp(TERM_WORD, buffer) == 0) < break; >//Определяем длину слова length = strlen(buffer); //В том случае, если введено слов больше, чем длина массива, то //увеличиваем массив слов if (wordCounter >= size) < size += SIZE_INCREMENT; words = (char**) realloc(words, size*sizeof(char*)); >//Выделяем память непосредственно под слово //на 1 байт больше, так как необходимо хранить терминальный символ words[wordCounter] = (char*) malloc(length + 1); //Копируем слово из буффера по адресу, который //хранится в массиве указателей на слова strcpy(words[wordCounter], buffer); wordCounter++; > while(1); for (i = 0; i < wordCounter; i++) < printf("%s\n", words[i]); >_getch(); for (i = 0; i < wordCounter; i++) < free(words[i]); >free(words); >
Хочу обратить внимание, что мы при выделении памяти пишем sizeof(char*), потому что размер указателя на char не равен одному байту, как размер переменной типа char.
Ошибки при выделении памяти
1. Бывает ситуация, при которой память не может быть выделена. В этом случае функция malloc (и calloc) возвращает NULL. Поэтому, перед выделением памяти необходимо обнулить указатель, а после выделения проверить, не равен ли он NULL. Так же ведёт себя и realloc. Когда мы используем функцию free проверять на NULL нет необходимости, так как согласно документации free(NULL) не производит никаких действий. Применительно к последнему примеру:
#include #include #include #include #define TERM_WORD "end" #define SIZE_INCREMENT 10 void main() < char **words; char buffer[128]; unsigned wordCounter = 0; unsigned length; unsigned size = SIZE_INCREMENT; int i; if (!(words = (char**) malloc(size*sizeof(char*)))) < printf("Error: can't allocate memory"); _getch(); exit(1); >do < printf("%d: ", wordCounter); scanf("%127s", buffer); if (strcmp(TERM_WORD, buffer) == 0) < break; >length = strlen(buffer); if (wordCounter >= size) < size += SIZE_INCREMENT; if (!(words = (char**) realloc(words, size*sizeof(char*)))) < printf("Error: can't reallocate memory"); _getch(); exit(2); >> if (!(words[wordCounter] = (char*)malloc(length + 1))) < printf("Error: can't allocate memory"); _getch(); exit(3); >strcpy(words[wordCounter], buffer); wordCounter++; > while(1); for (i = 0; i < wordCounter; i++) < printf("%s\n", words[i]); >_getch(); for (i = 0; i < wordCounter; i++) < free(words[i]); >free(words); >
Хотелось бы добавить, что ошибки выделения памяти могут случиться, и просто выходить из приложения и выкидывать ошибку плохо. Решение зависит от ситуации. Например, если не хватает памяти, то можно подождать некоторое время и после этого опять попытаться выделить память, или использовать для временного хранения файл и переместить туда часть объектов. Или выполнить очистку, сократив используемую память и удалив ненужные объекты.
2. Изменение указателя, который хранит адрес выделенной области памяти. Как уже упоминалось выше, в выделенной области хранятся данные об объекте — его размер. При удалении free получает эту информацию. Однако, если мы изменили указатель, то удаление приведёт к ошибке, например
#include #include #include void main() < int *p = NULL; if (!(p = (int*) malloc(100 * sizeof(int)))) < printf("Error"); exit(1); >//Изменили указатель p++; //Теперь free не может найти метаданные об объекте free(p); //На некоторых компиляторах ошибки не будет _getch(); >
Таким образом, если указатель хранит адрес, то его не нужно изменять. Для работы лучше создать дополнительную переменную указатель, с которой работать дальше.
3. Использование освобождённой области. Почему это работает в си, описано выше. Эта ошибка выливается в другую – так называемые висячие указатели (dangling pointers или wild pointers). Вы удаляете объект, но при этом забываете изменить значение указателя на NULL. В итоге, он хранит адрес области памяти, которой уже нельзя воспользоваться, при этом проверить, валидная эта область или нет, у нас нет возможности.
#include #include #include #define SIZE 10 void main() < int *p = NULL; int i; p = (int*) malloc(SIZE * sizeof(int)); for (i = 0; i < SIZE; i++) < p[i] = i; >free(p); for (i = 0; i < SIZE; i++) < printf("%i ", p[i]); >_getch(); >
Эта программа отработает и выведет мусор, или не мусор, или не выведет. Поведение не определено.
Если же мы напишем
free(p); p = NULL;
то программа выкинет исключение. Это определённо лучше, чем неопределённое поведение. Если вы освобождаете память и используете указатель в дальнейшем, то обязательно обнулите его.
4. Освобождение освобождённой памяти. Пример
#include #include void main()
Здесь дважды вызывается free для переменной a. При этом, переменная a продолжает хранить адрес, который может далее быть передан кому-нибудь для использования. Решение здесь такое же как и раньше — обнулить указатель явно после удаления:
#include #include void main() < int *a, *b; a = (int*) malloc(sizeof(int)); free(a); a = NULL; b = (int*) malloc(sizeof(int)); free(a);//вызов free(NULL) ничего не делает free(b); b = NULL; _getch(); >
5. Одновременная работа с двумя указателями на одну область памяти. Пусть, например, у нас два указателя p1 и p2. Если под первый указатель была выделена память, то второй указатель может запросто скомпрометировать эту область:
#include #include #include #define SIZE 10 void main() < int *p1 = NULL; int *p2 = NULL; size_t i; p1 = malloc(sizeof(int) * SIZE); p2 = p1; for (i = 0; i < SIZE; i++) < p1[i] = i; >p2 = realloc(p1, SIZE * 5000 * sizeof(int)); for (i = 0; i < SIZE; i++) < printf("%d ", p1[i]); >printf("\n"); for (i = 0; i < SIZE; i++) < printf("%d ", p2[i]); >_getch(); >
Рассмотрим код ещё раз.
int *p1 = NULL; int *p2 = NULL; size_t i; p1 = malloc(sizeof(int) * SIZE); p2 = p1;
Теперь оба указателя хранят один адрес.
p2 = realloc(p1, SIZE * 5000 * sizeof(int));
А вот здесь происходит непредвиденное. Мы решили выделить под p2 новый участок памяти. realloc гарантирует сохранение контента, но вот сам указатель p1 может перестать быть валидным. Есть разные ситуации. Во-первых, вызов malloc мог выделить много памяти, часть которой не используется. После вызова ничего не поменяется и p1 продолжит оставаться валидным. Если же потребовалось перемещение объекта, то p1 может указывать на невалидный адрес (именно это с большой вероятностью и произойдёт в нашем случае). Тогда p1 выведет мусор (или же произойдёт ошибка, если p1 полезет в недоступную память), в то время как p2 выведет старое содержимое p1. В этом случае поведение не определено.
Два указателя на одну область памяти это вообще-то не ошибка. Бывают ситуации, когда без них не обойтись. Но это очередное минное поле для программиста.
Различные аргументы realloc и malloc.
При вызове функции malloc, realloc и calloc с нулевым размером поведение не определено. Это значит, что может быть возвращён как NULL, так и реальный адрес. Им можно пользоваться, но к нему нельзя применять операцию разадресации.
Вызов realloc(NULL, size_t) эквиваленте вызову malloc(size_t).
Однако, вызов realloc(NULL, 0) не эквивалентен вызову malloc(0) 🙂 Понимайте это, как хотите.
Примеры
1. Простое скользящее среднее равно среднему арифметическому функции за период n. Пусть у нас имеется ряд измерений значения функции. Часто эти измерения из-за погрешности «плавают» или на них присутствуют высокочастотные колебания. Мы хотим сгладить ряд, для того, чтобы избавиться от этих помех, или для того, чтобы выявить общий тренд. Самый простой способ: взять n элементов ряда и получить их среднее арифметическое. n в данном случае — это период простого скользящего среднего. Так как мы берём n элементов для нахождения среднего, то в результирующем массиве будет на n чисел меньше.
Пусть есть ряд
1, 4, 4, 6, 7, 8, 9, 11, 12, 11, 15
Тогда если период среднего будет 3, то мы получим ряд
(1+4+4)/3, (4+4+6)/3, (4+6+7)/3, (6+7+8)/3, (7+8+9)/3, (8+9+11)/3, (9+11+12)/3, (11+12+11)/3, (12+11+15)/3
Видно, что сумма находится в «окне», которое скользит по ряду. Вместо того, чтобы каждый раз в цикле находить сумму, можно найти её для первого периода, а затем вычитать из суммы крайнее левое значение предыдущего периода и прибавлять крайнее правое значение следующего.
Будем запрашивать у пользователя числа и период, а затем создадим новый массив и заполним его средними значениями.
#include #include #include #define MAX_INCREMENT 20 void main() < //Считанные числа float *numbers = NULL; //Найденные значения float *mean = NULL; float readNext; //Максимальный размер массива чисел unsigned maxSize = MAX_INCREMENT; //Количество введённых чисел unsigned curSize = 0; //Строка для считывания действия char next[2]; //Шаг unsigned delta; //float переменная для хранения шага float realDelta; unsigned i, j; //Сумма чисел float sum; numbers = (float*) malloc(maxSize * sizeof(float)); do < //Пока пользователь вводит строку, которая начинается с y или Y, //то продолжаем считывать числа printf("next? [y/n]: "); scanf("%1s", next); if (next[0] == 'y' || next[0] == 'Y') < printf("%d. ", curSize); scanf("%f", &readNext); if (curSize >= maxSize) < maxSize += MAX_INCREMENT; numbers = (float*) realloc(numbers, maxSize * sizeof(float)); >numbers[curSize] = readNext; curSize++; > else < break; >> while(1); //Считываем период, он должен быть меньше, чем //количество элементов в массиве. Если оно равно, //то результатом станет среднее арифметическое всех введённых чисел do < printf("enter delta (>=%d): ", curSize); scanf("%d", &delta); if (delta > while(1); realDelta = (float) delta; //Находим среднее для первого периода mean = (float*) malloc(curSize * sizeof(float)); sum = 0; for (i = 0; i < delta; i++) < sum += numbers[i]; >//Среднее для всех остальных mean[0] = sum / delta; for (i = delta, j = 1; i < curSize; i++, j++) < sum = sum - numbers[j-1] + numbers[i]; mean[j] = sum / realDelta; >//Выводим. Чисел в массиве mean меньше на delta curSize = curSize - delta + 1; for (i = 0; i < curSize; i++) < printf("%.3f ", mean[i]); >free(numbers); free(mean); _getch(); >
Это простой пример. Большая его часть связана со считыванием данных, вычисление среднего всего в девяти строчках.
2. Сортировка двумерного массива. Самый простой способ сортировки — перевести двумерный массив MxN в одномерный размером M*N, после чего отсортировать одномерный массив, а затем заполнить двумерный массив отсортированными данными. Чтобы не тратить место под новый массив, мы поступим по-другому: если проходить по всем элементам массива k от 0 до M*N, то индексы текущего элемента можно найти следующим образом:
j = k / N;
i = k — j*M;
Заполним массив случайными числами и отсортируем
#include #include #include #include #define MAX_SIZE_X 20 #define MAX_SIZE_Y 20 void main() < int **mrx = NULL; int tmp; unsigned i, j, ip, jp, k, sizeX, sizeY, flag; printf("cols: "); scanf("%d", &sizeY); printf("rows: "); scanf("%d", &sizeX); //Если введённый размер больше MAX_SIZE_?, то присваиваем //значение MAX_SIZE_? sizeX = sizeX > //Выводим массив for (i = 0; i < sizeX; i++) < for (j = 0; j < sizeY; j++) < printf("%6d ", mrx[i][j]); >printf("\n"); > //Сортируем пузырьком, обходя все sizeX*sizeY элементы do < flag = 0; for (k = 1; k < sizeX * sizeY; k++) < //Вычисляем индексы текущего элемента j = k / sizeX; i = k - j*sizeX; //Вычисляем индексы предыдущего элемента jp = (k-1) / sizeX; ip = (k-1) - jp*sizeX; if (mrx[i][j] >mrx[ip][jp]) < tmp = mrx[i][j]; mrx[i][j] = mrx[ip][jp]; mrx[ip][jp] = tmp; flag = 1; >> > while(flag); printf("-----------------------\n"); for (i = 0; i < sizeX; i++) < for (j = 0; j < sizeY; j++) < printf("%6d ", mrx[i][j]); >free(mrx[i]); printf("\n"); > free(mrx); _getch(); >
3. Бином Ньютона. Создадим треугольную матрицу и заполним биномиальными коэффициентами
#include #include #include #define MAX_BINOM_HEIGHT 20 void main() < int** binom = NULL; unsigned height; unsigned i, j; printf("Enter height: "); scanf("%d", &height); height = height binom[0][0] = 1; for (i = 1; i < height; i++) < binom[i][0] = binom[i][i] = 1; for (j = i - 1; j >0; j--) < binom[i][j] = binom[i-1][j-1] + binom[i-1][j]; >> for (i = 0; i < height; i++) < for (j = 0; j free(binom[i]); printf("\n"); > free(binom); _getch(); >
Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик
Быстрое создание многомерных динамических массивов
В этом примере сначала выделяется память под массив указателей, потом M раз выделяется память под массивы. Во время удаления массива сначала M раз удаляются массивы, а потом удаляется массив указателей. Операции malloc и free затратные. Кроме того, выделение маленьких кусков памяти приводит к фрагментации памяти, так что последующее выделение памяти становится ещё медленнее.
Розовым обозначен массив указателей
Массив — это непрерывная последовательность байт. Массив не хранит своего размера. Указатель на массив хранит всего лишь адрес начала массива. Поэтому можно существенно ускорить выделение и освобождение памяти под массив. Выделяем сначала память под массив указателей, а затем первому элементу выделяем память под все массивы одновременно. Таким образом, первый элемент будет хранить адрес начала этого массива. С его помощью «делим» массив, раздавая его оставшимся указателям.
const int M = 100; const int N = 200; int **a = NULL; int i; a = (int**) malloc(M * sizeof(int*)); a[0] = (int*) malloc(M * N * sizeof(int)); for (i = 1; i < M; i++) < a[i] = a[0] + i * N; >//Важные действия free(a[0]); free(a);
Теперь нам необходимо всего две операции выделения памяти и две операции для освобождения.
Розовым обозначен массив указателей
У этого подхода есть и ещё одно важное преимущество. Массив a[0] по структуре становится похож на одномерный, так что его можно передавать как одномерный, например, для сортировки. Элементы расположены в нём по рядам, как в двумерном статическом массиве, поэтому без проблем можно его привести к типу указателя на массивы.
Можно пойти ещё дальше и заменить всё одним вызовом malloc: упаковать друг за другом сначала массив указателей, а потом массив массивов.
const int M = 100; const int N = 200; int **a = NULL; int i, j; a = (int**) malloc(M * sizeof(int*) + N * M * sizeof(int)); a[0] = (int*)(a + M); for (i = 1; i < M; i++) < a[i] = a[0] + i * N; >//Важные действия free(a);
Здесь всего одна операция выделения и одна освобождения.
Розовым обозначен массив указателей
Для массивов более высокой размерности выделение памяти остаётся очень похожим.
Скорость выполнения соотносится для данных способов выделения памяти как 404:13:12 для массива размером 100 x 200 типа int. Последние два способа выделения памяти, дабы не смущать неокрепшие умы, почти не используются в курсе, но на практике динамически выделять память под многомерные массивы лучше именно таким образом.
Рассмотрим выделение памяти под трёхмерный массив. Трёхмерный массив — массив указателей на указатели, которые ссылаются на массивы указателей, которые ссылаются на массивы объектов заданного типа. Выделение памяти под трёхмерный массив размером M*N*K, соответственно, потребует M + M*N операций выделения памяти и столько же для освобождения.
Серым обозначен массив указателей на указатели, розовым массив указателей
Первым делом объявим переменные
const int M = 10; const int N = 10; const int K = 10; int*** a = NULL; int* data; int** ptrs; int i, j, k;
Здесь a — наш будущий трёхмерный массив, data — вспомогательная переменная, которая хранит адрес, по которому начинаются непосредственно данные (белым цветом на рисунке). ptrs — вспомогательная переменная, которая хранит адрес, по которому начинаются массивы указателей (розовый на рисунке).
Для начала выделим память под массив
a = (int***) malloc(M * sizeof(int**) + M*N * sizeof(int*) + M*N*K * sizeof(int));
Затем инициализируем вспомогательные переменные
ptrs = (int**) (a + M); data = (int*) (a + M + M*N);
Затем надо инициализировать массив указателей на указатели
for (i = 0; i
Но также нужно инициализировать каждый из массивов указателей
for (i = 0; i < M; i++) < a[i] = ptrs + i*N; for (j = 0; j < N; j++) < a[i][j] = data + j * N*K; >>
Теперь наш массив принимает вид:
Серым обозначен массив указателей на указатели, розовым массив указателей
const int M = 10; const int N = 10; const int K = 10; int*** a = NULL; int* data; int** ptrs; int i, j, k, q; a = (int***) malloc(M * sizeof(int**) + M*N * sizeof(int*) + M*N*K * sizeof(int)); ptrs = (int**) (a + M); data = (int*) (a + M + M*N); q = 0; for (i = 0; i < M; i++) < a[i] = ptrs + i*N; for (j = 0; j < N; j++) < a[i][j] = data + (q++) * N*K; >>
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик