Содержание
malloc
В предыдущей главе уже обсуждалось, что локальные переменные кладутся на стек и существую до тех пор, пока мы не вышли из функции. С одной стороны, это позволяет автоматически очищать память, с другой стороны, существует необходимость в переменных, время жизни которых мы можем контролировать самостоятельно. Кроме того, нам необходимо динамическое выделение памяти, когда размер используемого пространства заранее не известен. Для этого используется выделение памяти на куче. Недостатков у такого подхода два: во-первых, память необходимо вручную очищать, во-вторых, выдеение памяти – достаточно дорогостоящая операция.
Для выделения памяти на куче в си используется функция malloc (memory allocation) из библиотеки stdlib.h
Функция выделяет size байтов памяти и возвращает указатель на неё. Если память выделить не удалось, то функция возвращает NULL. Так как malloc возвращает указатель типа void, то его необходимо явно приводить к нужному нам типу. Например, создадим указатель, после этого выделим память размером в 100 байт.
После того, как мы поработали с памятью, необходимо освободить память функцией free.
Используя указатель, можно работать с выделенной памятью как с массивом. Пример: пользователь вводит число – размер массива, создаём массив этого размера и заполняем его квадратами чисел по порядку. После этого выводим и удаляем массив.
Здесь (int *) – приведение типов. Пишем такой же тип, как и у указателя.
size * sizeof(int) – сколько байт выделить. sizeof(int) – размер одного элемента массива.
После этого работаем с указателем точно также, как и с массивом. В конце не забываем удалять выделенную память.
Теперь представим на рисунке, что у нас происходило. Пусть мы ввели число 5.
Функция malloc выделила память на куче по определённому адресу, после чего вернула его. Теперь указатель p хранит этот адрес и может им пользоваться для работы. В принципе, он может пользоваться и любым другим адресом.
Когда функция malloc "выделяет память", то она резервирует место на куче и возвращает адрес этого участка. У нас будет гарантия, что компьютер не отдаст нашу память кому-то ещё. Когда мы вызываем функцию free, то мы освобождаем память, то есть говорим компьютеру, что эта память может быть использована кем-то другим. Он может использовать нашу память, а может и нет, но теперь у нас уже нет гарантии, что эта память наша. При этом сама переменная не зануляется, она продолжает хранить адрес, которым ранее пользовалась.
Это очень похоже на съём номера в отеле. Мы получаем дубликат ключа от номера, живём в нём, а потом сдаём комнату обратно. Но дубликат ключа у нас остаётся. Всегда можно зайти в этот номер, но в нём уже кто-то может жить. Так что наша обязанность – удалить дубликат.
Иногда думают, что происходит "создание" или "удаление" памяти. На самом деле происходит только перераспределение ресурсов.
Освобождение памяти с помощью free
Т еперь рассмотри, как происходит освобождение памяти. Переменная указатель хранит адрес области памяти, начиная с которого она может им пользоваться. Однако, она не хранит размера этой области. Откуда тогда функция free знает, сколько памяти необходимо освободить?
Очевидно, что информация о размере выделенного участка должна где-то храниться. Есть несколько решения этой проблемы.
- 1. Можно создать карту, в которой будет храниться размер выделенного участка. Каждый раз при освобождении памяти компьютер будет обращаться к этим данным и получать нужную информацию.
- 2. Второе решение более распространено. Информация о размере хранится на куче до самих данных. Таким образом, при выделении памяти резервируется места больше и туда записывается информация о выделенном участке. При освобождении памяти функция free "подсматривает", сколько памяти необходимо удалить.
Функция free освобождает память, но при этом не изменяет значение указателя, о чём нужно помнить.
Работа с двумерными и многомерными массивами
Д ля динамического создания двумерного массива сначала необходимо создать массив указателей, после чего каждому из элементов этого массива присвоить адрес нового массива.
Для удаления массива необходимо повторить операцию в обратном порядке — удалить сначала подмассивы, а потом и сам массив указателей.
Сначала мы создаём массив указателей, а после этого каждому элементу этого массива присваиваем адрес вновь созданного массива. Это значит, что можно
- 1. Создавать массивы "неправильной формы", то есть массив строк, каждая из которых имеет свой размер.
- 2. Работать по отдельности с каждой строкой массива: освобождать память или изменять размер строки.
Создадим "треугольный" массив и заполним его значениями
Чтобы создать трёхмерный массив, по аналогии, необходимо сначала определить указатель на указатель на указатель, после чего выделить память под массив указателей на указатель, после чего проинициализировать каждый из массивов и т.д.
calloc
Ф ункция calloc выделяет n объектов размером m и заполняет их нулями. Обычно она используется для выделения памяти под массивы. Синтаксис
realloc
Е щё одна важная функция – realloc (re-allocation). Она позволяет изменить размер ранее выделенной памяти и получает в качестве аргументов старый указатель и новый размер памяти в байтах:
Функция realloc может как использовать ранее выделенный участок памяти, так и новый. При этом не важно, меньше или больше новый размер – менеджер памяти сам решает, где выделять память.
Пример – пользователь вводит слова. Для начала выделяем под слова массив размером 10. Если пользователь ввёл больше слов, то изменяем его размер, чтобы хватило места. Когда пользователь вводит слово end, прекращаем ввод и выводим на печать все слова.
Хочу обратить внимание, что мы при выделении памяти пишем sizeof(char*), потому что размер указателя на char не равен одному байту, как размер переменной типа char.
Ошибки при выделении памяти
1. Бывает ситуация, при которой память не может быть выделена. В этом случае функция malloc (и calloc) возвращает NULL. Поэтому, перед выделением памяти необходимо обнулить указатель, а после выделения проверить, не равен ли он NULL. Так же ведёт себя и realloc. Когда мы используем функцию free проверять на NULL нет необходимости, так как согласно документации free(NULL) не производит никаких действий. Применительно к последнему примеру:
Хотелось бы добавить, что ошибки выделения памяти могут случиться, и просто выходить из приложения и выкидывать ошибку плохо. Решение зависит от ситуации. Например, если не хватает памяти, то можно подождать некоторое время и после этого опять попытаться выделить память, или использовать для временного хранения файл и переместить туда часть объектов. Или выполнить очистку, сократив используемую память и удалив ненужные объекты.
2. Изменение указателя, который хранит адрес выделенной области памяти. Как уже упоминалось выше, в выделенной области хранятся данные об объекте — его размер. При удалении free получает эту информацию. Однако, если мы изменили указатель, то удаление приведёт к ошибке, например
Таким образом, если указатель хранит адрес, то его не нужно изменять. Для работы лучше создать дополнительную переменную указатель, с которой работать дальше.
3. Использование освобождённой области. Почему это работает в си, описано выше. Эта ошибка выливается в другую – так называемые висячие указатели (dangling pointers или wild pointers). Вы удаляете объект, но при этом забываете изменить значение указателя на NULL. В итоге, он хранит адрес области памяти, которой уже нельзя воспользоваться, при этом проверить, валидная эта область или нет, у нас нет возможности.
Эта программа отработает и выведет мусор, или не мусор, или не выведет. Поведение не определено.
Если же мы напишем
то программа выкинет исключение. Это определённо лучше, чем неопределённое поведение. Если вы освобождаете память и используете указатель в дальнейшем, то обязательно обнулите его.
4. Освобождение освобождённой памяти. Пример
Здесь дважды вызывается free для переменной a. При этом, переменная a продолжает хранить адрес, который может далее быть передан кому-нибудь для использования. Решение здесь такое же как и раньше — обнулить указатель явно после удаления:
5. Одновременная работа с двумя указателями на одну область памяти. Пусть, например, у нас два указателя p1 и p2. Если под первый указатель была выделена память, то второй указатель может запросто скомпрометировать эту область:
Рассмотрим код ещё раз.
Теперь оба указателя хранят один адрес.
А вот здесь происходит непредвиденное. Мы решили выделить под 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
Видно, что сумма находится в "окне", которое скользит по ряду. Вместо того, чтобы каждый раз в цикле находить сумму, можно найти её для первого периода, а затем вычитать из суммы крайнее левое значение предыдущего периода и прибавлять крайнее правое значение следующего.
Будем запрашивать у пользователя числа и период, а затем создадим новый массив и заполним его средними значениями.
Это простой пример. Большая его часть связана со считыванием данных, вычисление среднего всего в девяти строчках.
2. Сортировка двумерного массива. Самый простой способ сортировки — перевести двумерный массив MxN в одномерный размером M*N, после чего отсортировать одномерный массив, а затем заполнить двумерный массив отсортированными данными. Чтобы не тратить место под новый массив, мы поступим по-другому: если проходить по всем элементам массива k от 0 до M*N, то индексы текущего элемента можно найти следующим образом:
j = k / N;
i = k — j*M;
Заполним массив случайными числами и отсортируем
3. Бином Ньютона. Создадим треугольную матрицу и заполним биномиальными коэффициентами
Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике
У меня есть массив структур. Я пытаюсь удалить список элементов из этого массива и сдвинуть другие элементы влево. После смещения элементов я пытаюсь удалить / освободить память в конце массива, который нам больше не нужен. У меня есть следующий код:
Но delete [] array[j+1]; вызывает исключение:
Я не понимаю, что является причиной этого. Как многие люди предлагали на других форумах, я использую оператор «new» для создания нового динамического элемента.
РЕДАКТИРОВАТЬ:
Я сделал следующие изменения:
Я изменился for(j=index;j в for(j=index;j
int index = removelist[i] в int index = removelist[i]-i
Я удалил delete [] array[j+1] положил delete array[numofelements+1] снаружи как для петель.
Хотя я использовал delete только для одного элемента, он освободил память и для других избыточных элементов, что интересно.
Это окончательный код:
Я получил его с помощью этого кода. Но я собираюсь использовать std :: vector, как многие из вас предложили.
Решение
Помимо очевидных ошибок в управлении памятью, подход в целом можно было бы упростить, если бы вы сначала отсортировали removelist массив, а затем работать в обратном направлении в этом массиве, начиная с последней записи по направлению к первой записи.
Это изменило бы способ array было изменено в том смысле, что вы делали изменение размера (смещение элементов) для записей, которые больше не будут затронуты. В вашем текущем коде вы перемещаете записи, и в последующих итерациях цикла вам необходимо повторно просмотреть эти сдвинутые записи с теперь «недействительным» removelist набор показателей для удаления.
См. Ответы mayaknife и user2079303, чтобы проиллюстрировать проблему недействительных записей после удаления каждого элемента (переход от самой низкой записи к самой высокой записи в removelist массив). Как указывалось, даже использование std::vector не помог бы вам, так как эта проблема указывает на недостаток в базовой логике, используемой для удаления элементов.
Вот как вы могли бы решить эту проблему в своем текущем коде, если бы вы работали в обратном направлении в removelist массив (я говорю «возможно, обратился», так как это не полностью проверено, но оно более или менее иллюстрирует сделанную точку):
Таким образом, на каждой итерации removelist Индекс будет по-прежнему действителен, так как вы переходите от самой высокой записи к самой низкой записи в записях, которые нужно удалить. Поработайте над этим на бумаге, и вы увидите, изменили ли вы способ, которым вы перебирали removelist массив, вы должны увидеть, как это работает, а не идти вперед через removelist массив.
У вас также есть другие проблемы с кодом, такие как смешивание malloc с delete[] , Это неопределенное поведение — никогда не смешивайте методы выделения / освобождения, подобные этим, в программе на C ++.
Сказав это, вот еще одна версия вашей программы, но без ручного управления памятью:
Обратите внимание на использование обратных итераторов rbegin() а также rend() таким образом, имитируя обратный обход removelist контейнер.
Другие решения
Ты использовал delete[] выражение на указателе, которое не было возвращено new[] выражение. Поэтому поведение программы не определено.
Все, что было выделено с new должен быть освобожден с delete , delete[] не будет делать.
Даже если вы использовали правильное выражение, есть еще одна ошибка:
После первой итерации внешнего цикла array[4] был удален. Обратите внимание, что с removelist[i] == 1 Подозреваю что array[4] не должен был быть удален в первую очередь.
Во время второй итерации array[4] будет удален снова. Поскольку это указывает на уже удаленный объект, поведение не определено.
Кроме того, копии удаленного указателя остаются в массиве из-за array[j] = array[j+1] во внутреннем цикле, в то время как некоторые из указателей будут перезаписаны и, следовательно, их память будет просочиться. Простое исправление в вашем алгоритме: сначала удалите указатель на индекс, а затем сдвиньте элементы.
Более того: если бы ваш цикл работал так, как вы планировали, первые две итерации удалили бы каждый элемент массива, уменьшив тем самым numofelements 3. Затем вы удалите элемент с индексом 4 массива, который имеет действительные указатели в индексах 0..2. Предположительно, подлежащие удалению индексы должны быть отсортированы; В этом случае это можно исправить, удалив индекс removelist[i] — i учитывать смены. Еще одна умная стратегия — убрать индексы с максимума на минимум, как полагает Пол.
Другие вещи для рассмотрения:
- Программа пропускает память, выделенную для array , Это может не быть проблемой для этой тривиальной программы, но было бы неплохо иметь привычку освобождать всю выделенную память, чтобы вы не забыли сделать это, когда это важно.
- Это плохая идея для использования malloc если только у человека нет конкретного и разумного обоснования для этого. У одного обычно нет разумного оправдания для использования malloc ,
- Плохо выделять динамическую память вообще без использования контейнера RAII. Ошибок в этой программе можно было бы избежать, если бы std::vector был использован.
удаляет массив элементов, на которые указывает ‘array [j + 1]’. Но ‘array [j + 1]’ был инициализирован этой строкой:
который выделяет только один элемент, а не массив элементов, поэтому удаление должно также удалить только один элемент. Например:
Основная проблема, однако, заключается в том, что неправильные элементы удаляются. Чтобы понять почему, давайте предположим, что цикл, который инициализирует «массив», назначает указатели на пять «элементных» структур, которые мы будем называть A, B, C, D и E.
Перед вызовом removeelements (), массив содержит следующие указатели:
Внутри removeelements () первый удаляемый элемент равен 1, а внутренний цикл выглядит следующим образом:
Это приведет к тому, что содержимое «array [2]» будет скопировано в «array [1]», а «array [3]» будет скопировано в «array [2]». После этого «массив» содержит следующее:
В этот момент «j» содержит 3, поэтому «delete array [j + 1]» удалит элемент, на который указывает «array [4]», то есть «E».
numofelements затем уменьшается до 4.
Второй удаляемый элемент — 3. Поскольку numofelements теперь равно 4, внутренний цикл будет выглядеть следующим образом:
‘j’ будет инициализировано 3. Это больше 2, поэтому тело цикла не будет выполнено, а ‘массив’ останется неизменным.
Поскольку «j» равен 3, «удалить массив [j + 1]» снова удалит «массив [4]», который все еще указывает на E. Таким образом, E удаляется во второй раз, что приводит к получаемой вами ошибке.
Если бы программа продолжалась, numofelements был бы уменьшен до 3, и мы бы перешли к третьему элементу, который нужно удалить, который был бы 4. Это дало бы внутренний цикл, подобный этому:
‘j’ будет инициализировано значением 4, и снова тело цикла не будет выполнено. «delete array [j + 1]» будет пытаться удалить элемент, на который указывает «array [5]», что выходит за границы «array» и приведет к исключению.
Как и предполагали другие, лучший способ справиться с этим — использовать std :: vector. Однако то, как ваш код структурирован даже в std :: vector, не даст желаемых результатов, потому что как только вы удаляете один элемент из «массива», индексы всех последующих элементов изменяются, а это означает, что остальные индексы в «списке удаления» больше не будут правильными.
Я предлагаю, чтобы какие бы изменения вы ни делали, вы вручную проходите по коду, как я делал выше, отслеживая содержимое массива и соответствующие переменные, чтобы вы могли точно понять, что делает ваш код.
Обычно, объем памяти, необходимый для той или иной переменной, задается еще до процесса компиляции посредством объявления этой переменной. Если же возникает необходимость в создание переменной, размер которой неизвестен заранее, то используют динамическую память. Резервирование и освобождение памяти в программах на C++ может происходить в любой момент времени. Осуществляются операции распределения памяти двумя способами:
- с помощью функции malloc, calloc, realloc и free;
- посредством оператора new и delete.
Функция malloc резервирует непрерывный блок ячеек памяти для хранения указанного объекта и возвращает указатель на первую ячейку этого блока. Обращение к функции имеет вид:
void *malloc(size);
Здесь size — целое беззнаковое значение, определяющее размер выделяемого участка памяти в байтах. Если резервирование памяти прошло успешно, то функция возвращает переменную типа void *, которую можно привести к любому необходимому типу указателя.
Функция — calloc также предназначена для выделения памяти. Запись ниже означает, что будет выделено num элементов по size байт.
void *calloc (nime, size);
Эта функция возвращает указатель на выделенный участок или NULL при невозможности выделить память. Особенностью функции является обнуление всех выделенных элементов.
Функция realloc изменяет размер выделенной ранее памяти. Обращаются к ней так:
char *realloc (void *p, size);
Здесь p — указатель на область памяти, размер которой нужно изменить на size. Если в результате работы функции меняется адрес области памяти, то новый адрес вернется в качестве результата. Если фактическое значение первого параметра NULL, то функция realloc работает также, как и функция malloc, то есть выделяет участок памяти размером size байт.
Для освобождения выделенной памяти используется функция free. Обращаются к ней так:
void free (void *p size);
Здесь p — указатель на участок памяти, ранее выделенный функциями malloc, calloc или realloc.
Операторы new и delete аналогичны функциям malloc и free. New выделяет память, а его единственный аргумент — это выражение, определяющее количество байтов, которые будут зарезервированы. Возвращает оператор указатель на начало выделенного блока памяти. Оператор delete освобождает память, его аргумент — адрес первой ячейки блока, который необходимо освободить.
Динамический массив — массив переменной длины, память под который выделяется в процессе выполнения программы. Выделение памяти осуществляется функциями calloc, malloc или оператором new. Адрес первого элемента выделенного участка памяти хранится в переменной, объявленной как указатель. Например, следующий оператор означает, что описан указатель mas и ему присвоен адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new:
int *mas=new int[10];
Выделено столько памяти, сколько необходимо для хранения 10 величин типа int.
Фактически, в переменной mas хранится адрес нулевого элемента динамического массива. Следовательно, адрес следующего, первого элемента, в выделенном участке памяти — mas+1, а mas+i является адресом i-го элемента. Обращение к i-му элементу динамического массива можно выполнить, как обычно mas[i], или другим способом *(mas +i). Важно следить за тем, чтобы не выйти за границы выделенного участка памяти.
Когда динамический массив (в любой момент работы программы) перестает быть нужным, то память можно освободить с помощью функции free или оператора delete.
Предлагаю рассмотреть несколько задач, закрепляющих данный урок:
Задача 1
Найти сумму вещественных элементов динамического массива.
