При решении ряда задач становится неудобно, неэффективно, а иногда и просто невозможно обойтись использованием памяти, выделяемой компилятором и системой поддержки времени выполнения в соответствии с явными описаниями переменных в программе. Во всех языках, более или менее приспособленных к практическому применению, имеется возможность явно запрашивать и использовать области так называемой динамической памяти. Такие области принято называть "динамическими переменными". Возможности создания и использования динамических переменных тесно связаны с механизмами указателей, поскольку динамическая переменная не имеет статически заданного имени, и доступ к такой переменной возможен только через указатель.
Как и во многих обсуждавшихся ранее случаях, механизмы работы с динамической памятью в языках с сильной типизацией существенно отличаются от соответствующих механизмов языков со слабой типизацией. В языках линии Паскаль для запроса динамических переменных используется встроенная процедура new(var), где var – переменная некоторого ссылочного типа T. Если тип T определялся конструкцией type T = T0, то при выполнении этой процедуры подсистема поддержки времени выполнения выделяет динамическую область памяти с размером, достаточным для размещения переменных типа T0, и переменной var присваивается ссылочное значение, обеспечивающее доступ к выделенной динамической переменной.
Понятно, что размеры области памяти, используемой для динамического выделения переменных, в любой реализации языка ограничены. Кроме того, обычно время полезного существования динамической переменной меньше времени выполнения программы, в которой эта переменная была создана. Поэтому наряду со средствами образования динамических переменных должны существовать средства освобождения памяти, занятой ставшими бесполезными динамическими переменными. В сильно типизированных языках для этого применяются два разных механизма.
Первый – это явное использование встроенной процедуры dispose(var), где var – переменная ссылочного типа, значение которой указывает на ранее выделенную и еще не освобожденную динамическую переменную. Строго говоря, при выполнении процедуры dispose должно быть не только произведено действие по освобождению памяти, но также переменной var и всем переменным того же ссылочного типа с тем же значением должно быть присвоено значение nil. Это гарантировало бы, что после вызова dispose в программе были бы невозможны некорректные обращения к освобожденной области памяти. К сожалению, обычно из соображений эффективности такая глобальная очистка не производится, и программирование с использованием динамической памяти становится достаточно опасным.
Второй механизм, обеспечивающий более безопасное программирование, состоит в том, что подсистема поддержки времени выполнения хранит ссылки на все выделенные динамические переменные и время от времени (обычно, когда объем свободной динамической памяти достигает некоторого нижнего предела) автоматически запускает процедуру "сборки мусора". Процедура просматривает содержимое всех существующих к этому моменту ссылочных переменных, и если оказывается что некоторые ссылки не являются значением ни одной ссылочной переменной, освобождает соответствующие области динамической памяти. Заметим, что это является возможным в силу наличия строгой типизации ссылочных переменных и отсутствия явных или неявных преобразований их типов.
Работа с динамической памятью в языках Си/Си++ гораздо проще и опаснее. Правильнее сказать, что в самих языках средства динамического выделения и освобождения памяти вообще отсутствуют. При программировании на языке Си для этих целей используются несколько функций из стандартной библиотеки stdlib, специфицированной в стандарте ANSI C. При реализации языка Си в среде ОС UNIX используются соответствующие функции из системной библиотеки stdlib.
Базовой функцией для выделения памяти является malloc(), входным параметром которой является размер требуемой области динамической памяти в байтах, а выходным – значение типа *void, указывающее на первый байт выделенной области. Гарантируется, что размер выделенной области будет не меньше запрашиваемого и что область будет выравнена так, чтобы в ней можно было корректно разместить значение любого типа данных. Тем самым, чтобы использовать значение, возвращаемое функцией malloc(), необходимо явно преобразовать его тип к нужному указательному типу.
Для освобождения ранее выделенной области динамической памяти используется функция free(). Ее входным параметром является значение типа *void, которое должно указывать на начало ранее выделенной динамической области. Поведение программы непредсказуемо при использовании указателей на ранее освобожденную память и при задании в качестве параметра функции free() некорректного значения.
Заметим, что по причине наличия возможности получить значение указателя на любую статически объявленную переменную, работа с указателями на статические и динамические переменные производится полностью единообразно. Единообразная работа с массивами и указателями естественным образом позволяет создавать и использовать динамические массивы.
Как видно, с динамической памятью в языках Си/Си++ работать можно очень эффективно, но программирование является опасным.
Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти – списки, деревья, графы и т.д. (Особенности указателей в языках Си/Си++ позволяют, вообще говоря, строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных.) Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип T, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная var типа T (или переменная типа указателя на T в случае полностью динамического создания структуры). Имя этой переменной при выполнении программы используется как имя "корня" динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной var (или первой динамической переменной, указатель на которую содержится в переменной var). Понятно, что этот подход позволяет создать динамическую структуру с любой топологией.
Наиболее простой динамической структурой является однонаправленный список (рисунок 1.1). Для создания списка определяется структурный тип T, у которого имеется одно поле next, объявленное как указатель на T. Другие поля структуры содержат информацию, характеризующую элемент списка. При образовании первого элемента ("корня") списка в поле next заносится пустой указатель (nil или NULL). При дальнейшем построении списка это значение будет присутствовать в последнем элементе списка
Над списком, построенном в такой манере, можно выполнять операции поиска элемента, удаления элемента и занесение нового элемента в начало, конец или середину списка. Понятно, что все эти операции будут выполняться путем манипуляций над содержимым поля next существующих элементов списка. Для оптимизации операций над списком иногда создают вспомогательную переменную-структуру (заголовок списка), состоящую из двух полей – указателей на первый и последний элементы списка (рисунок 1.2). Для этих же целей создают двунаправленные списки, элементы которых, помимо поля next, включают поле previous, содержащее указатель на предыдущий элемент списка (рисунок 1.3) и, возможно, ссылки на заголовок списка (рисунок 1.4).
