Средства выделения и освобождения памяти

В языке C++ существуют предусмотренные стандартом C++, а также перешедшие "в наследство" от C средства выделения и освобождения памяти. Кроме того, каждая платформа предоставляет свои средства управления памятью (как правило, стандартные языковые средства как раз к ним и обращаются, но у программиста есть возможность обратиться к ним непосредственно). Проблема этих систем и языков (в том числе C++) состоит в том, что программист сам отвечает за своевременное освобождение блоков памяти после того, как в них отпадает необходимость - для этого тоже есть специальные функции. Если программист забудет освободить блок, впоследствии может возникнуть нехватка памяти - виртуальное адресное пространство процесса "забьется" и свободного места не останется, хотя в то же время в памяти будут присутствовать блоки, которые фактически не используются.

Рассмотрим коротко средства управления памятью.

Оператор new очень удобен - он не требует указания размера блока, который нужно выделить. Размер определяется компилятором автоматически исходя из типа, который указывается после ключевого слова new. Кроме вызова самой функции выделения памяти происходит еще и вызов конструктора объекта, если указан объектный тип. Синтаксис вызова оператора имеет несколько вариантов, рассмотрим наиболее часто употребляемый:

new Type (parameters)

где Type - тип создаваемого объекта, на основе которого компилятор автоматически определит требуемый для него объем памяти;

parameters - необязательный список параметров, который будет передан конструктору объекта. В случае отсутствия списка параметров скобки указывать необязательно.

Функция malloc, доставшаяся языку C++ в наследство от C, требует указания необходимого количества байт и не производит кроме собственно выделения памяти никаких дополнительных действий.

Функции операционной системы Windows - LocalAlloc и GlobalAlloc - считаются устаревшими, хотя и поддерживаются в целях совместимости. Современным приложениям рекомендуется пользоваться HeapAlloc, а также VirtualAlloc, которая, помимо выделения памяти, поддерживает операцию резервирования памяти и выделения зарезервированной памяти.

Соответственно, средства освобождения памяти следующие.

Оператор delete освобождает занятый приложением блок, но перед этим вызывает деструктор объекта, если переменная объектного типа. Ничего, кроме параметра, содержащего адрес удаляемого блока, передавать не надо.

Функция free () освобождает выделенный с помощью malloc () блок. Следует передать адрес блока.

В языке C++ имеются средства создания динамических структур данных, которые позволяют во время выполнения программы образовывать объекты, выделять для них память, освобождать память, когда в них исчезает необходимость.

Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память следует распределять во время выполнения программы по мере необходимости отдельными блоками. Блоки связываются друг с другом с помощью указателей. Такой способ организации данных называется динамической структурой данных, поскольку она размещается в динамической памяти и ее размер изменяется во время выполнения программы.

Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости.

Динамические структуры данных в процессе существования в памяти могут изменять не только число составляющих их элементов, но и характер связей между элементами. При этом не учитывается изменение содержимого самих элементов данных. Такая особенность динамических структур, как непостоянство их размера и характера отношений между элементами, приводит к тому, что на этапе создания машинного кода программа-компилятор не может выделить для всей структуры в целом участок памяти фиксированного размера, а также не может сопоставить с отдельными компонентами структуры конкретные адреса. Для решения проблемы адресации динамических структур данных используется метод, называемый динамическим распределением памяти, то есть память под отдельные элементы выделяется в момент, когда они "начинают существовать" в процессе выполнения программы, а не во время компиляции. Компилятор в этом случае выделяет фиксированный объем памяти для хранения адреса динамически размещаемого элемента, а не самого элемента.

Необходимость в динамических структурах данных обычно возникает в следующих случаях.

1. Используются переменные, имеющие довольно большой размер (например, массивы большой размерности), необходимые в одних частях программы и совершенно не нужные в других.

2. В процессе работы программы нужен массив, список или иная структура, размер которой изменяется в широких пределах и трудно предсказуем.

3. Когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным.

Достоинства связного представления данных – в возможности обеспечения значительной изменчивости структур:

1. размер структуры ограничивается только доступным объемом машинной памяти;

2. при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей;

3. большая гибкость структуры.

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

1. на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;

2. доступ к элементам связной структуры может быть менее эффективным по времени.

Порядок работы с динамическими структурами данных следующий:

1. создать (отвести место в динамической памяти);

2. работать при помощи указателя;

3. удалить (освободить занятое структурой место).

Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.

Одним из видов динамической структуры является – список.

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным.

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

Список - это так называемая линейная структура данных, с помощью которой задаются одномерные отношения.

Список - структура данных, в которой каждый элемент имеет информационное поле (поля) и ссылку (ссылки), то есть адрес (адреса), на другой элемент (элементы) списка.

Каждый элемент списка содержит информационную и ссылочную части.

Порядок расположения информационных и ссылочных полей в элементе при его описании - по выбору программиста, то есть фактически произволен.

Информационная часть в общем случае может быть неоднородной, то есть содержать поля с информацией различных типов.

Ссылки однотипны, но число их может быть различным в зависимости от типа списка.

В связи с этим для описания элемента списка подходит тип «структура», так как этот тип данных может иметь разнотипные поля. Например, для однонаправленного списка элемент должен содержать как минимум два поля: одно поле типа «указатель», другое - для хранения данных пользователя. Для двунаправленного - три поля, два из которых должны быть типа «указатель».

Элементы массива располагаются в памяти в определенном постоянном порядке - подряд, друг за другом, что закрепляется их номерами. Каждый элемент массива имеет свое место, которое не может быть изменено, хотя значение элемента может изменяться. Порядок обработки элементов определяется использованием их номеров, индексов.

В отличие от элементов массива элементы списка могут располагаться в памяти в свободном порядке, не подряд.

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

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

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

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

Такая организация списка позволяет от каждого элемента двигаться по списку как в прямом, так и в обратном направлениях. Наиболее удобной при этом является та организация ссылок, при которой движение, перебор элементов в обратном направлении является строго противоположным перебору элементов в прямом направлении. В этом случае двунаправленный список называется симметричным. Например, в прямом направлении элементы линейного списка пронумерованы и выбираются так: 1, 2, 3, 4, 5. Строго говоря, перебирать элементы в обратном направлении можно по-разному, соответствующим способом организуя ссылки, например: 4, 1, 5, 3, 2. Симметричным же будет называться список, реализующий перебор элементов в таком порядке: 5, 4, 3, 2, 1.

Как указывалось ранее, замкнутый, циклический, кольцевой список организован таким образом, что в адресную часть конечного элемента вместо константы null помещается адрес начального элемента (список замыкается на себя). В симметричном кольцевом списке такое положение характерно для обоих - прямого и обратного - списков, следовательно, можно построить циклический двунаправленный список Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы (рис.1). При этом два соседних элемента должны содержать взаимные ссылки друг на друга.

В таком списке каждый элемент (кроме первого и последнего) связан с предыдущим и следующим за ним элементами. Каждый элемент двунаправленного списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле – информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют двунаправленным.

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле 1;

адресное поле 2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа; адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка ; адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.

При работе со списками любых видов нельзя обойтись без указателя на первый элемент. Не менее полезными, хотя и не всегда обязательными, могут стать адрес последнего элемента списка и количество элементов. Эти данные могут существовать по отдельности, однако их можно объединить в единый тип «структура» (из-за разнотипности полей: два поля указателей на элементы и числовое поле - для количества элементов). Эта структура и будет представлять так называемый головной элемент списка.

Следуя идеологии динамических структур данных, головной элемент списка также необходимо сделать динамическим, выделяя под него память при создании списка и освобождая после окончания работы. Тем не менее, стоит отметить, что головной элемент может быть и статического типа. Тогда он описывается в разделе VAR как обычная переменная типа RECORD соответствующей структуры.

Использование данных головного элемента делает работу со списком более удобной, но требует определенных действий по его обслуживанию.

Головной элемент содержит основные характеристики списка – адрес первого элемента, адрес последнего элемента, текущее количество элементов списка. Это даёт возможность не создавать и не применять постоянно подпрограммы определения текущего количества элементов списка, поиска адреса последнего элемента списка. Особенно наличие головного элемента облегчает работу с симметричным списком. Кроме того, при работе со списком циклы WHILE … DO и REPEAT…UNTIL могут быть заменены циклами FOR.

Структура головного элемента (приведен минимальный набор полей, последовательность их расположения произвольна)

First

N

Last

где:

1. First – адрес первого элемента списка;

2. Last - адрес последнего элемента списка;

3. N - текущее количество элементов списка;

Рис. 1. Двунаправленный список

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле 1;

адресное поле 2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа; адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка ; адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.

Головной элемент содержит основные характеристики списка – адрес первого элемента, адрес последнего элемента, текущее количество элементов списка. Это даёт возможность не создавать и не применять постоянно подпрограммы определения текущего количества элементов списка, поиска адреса последнего элемента списка. Особенно наличие головного элемента облегчает работу с симметричным списком. Кроме того, при работе со списком циклы WHILE … DO и REPEAT…UNTIL могут быть заменены циклами FOR.

Структура головного элемента (приведен минимальный набор полей, последовательность их расположения произвольна)

First

N

Last

где:

• First – адрес первого элемента списка;

• Last - адрес последнего элемента списка;

• N - текущее количество элементов списка;

Двунаправленный кольцевой список с головным элементом: