Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 69
Текст из файла (страница 69)
Например, произвольная выборка компонентов обыкновенного последовательного файла затруднена, если в представлении этой структуры 244 Глава 6. Инкапсуляция отсутствуют индексы (см. раздел 5.3.3). Другим примером являются хэш-таблицы для представления множеств. Управление ресурсами памяти и структуры данных Время жизни любого объекта ланных отсчитывается от того момента, когда проис- 1 ходит связывание объекта с конкретной областью памяти (то есть когда этому объекту отводится некоторый блок (или блоки) памяти и инициируется его размещение в памяти). Заканчивается время жизни, когда эта связь между обьектом и блоком памяти разрушается.
В случае обьектов данных переменного размера для каждого компонента время жизни определяется индивидуально. Оно отсчитывается от мок нта создания компонента внутри структуры данных и заканчивается, когда компонент удаляется из этой сгруктуры. В момент создания обьекта данных (то есть в начале времени жизни) создается также путь доступа к нему, который необходим для того, чтобы имеющиеся в программе операции могли обращаться к этому объекту данных.
Создание пути доступа происходит или через связывание объекта данных с некоторым идентификатором, который становится именем этого объекта в некоторой среде ссылок (см. главу 9), или через указа~ель на структуру в некоторой другой уже существующей и доступной структуре. В этом последнем случае наш объект данных становится компонентом некой старой структуры.
В течение времени жизни объекта могут быть созданы дополните.тьные пути доступа к нему, например, если этот объект передается в подпрограмму как параметр или если для него создаются новые указатели. Пути доступа могут быль уничтожены различными способами, в частности посредством присвоения указателю нового значения или при выходе из подпрограммы. Вследствие этого будет потеряна связь объекта со средой ссылок.
Таким образом, в течение времени жизни объекта может существовать несколько путей доступа к нему. несоответствие между временем жизни объекта и временем жизни путей доступа к нему порождаег две основные проблемы управления ресурсами памяти. 1. Мусор. 1<огда все пути доступа к объекту данных разрушены, но сам объект продолжает существовать, говорят, что он стал мусором. Мало того что к этому объекту данных другие программные конструкции больше не имеют доступа, он просто становится бесполезен. Поскольку связывание объекта с некотором блоком памяти осталось в силе, этот блок остается занят и недоступен для использования. 2.
Повисшие ссылки, Повисшая ссылка — это путь доступа, который продолжает существовать после истечения времени жизни ассоциированного с ним обьекта даняых. Путь доступа обычно указывает местоположение обьекта данных (то есть начальную позицию того блока памяти, в котором содержится объект), После завершения времени жизяи объекта этот блок восстанавливается для дальнейшего использования и впоследствии может быть отведен под какой-либо новый объект данных.
Тем не менее восстановление блока памяти для дальнейшего использования не обязательно влечет за собой разрушение всех существующих ссылок (то есть путей доступа), и, следовательно, они могут продолжать существовать как повисшие ссылки. 6.1. Структурированные типы данных 245 Повисшие ссылки представляют собой особенно серьезную проблему для управления ресурсами памяти, так как они могут нарушить целостность всей структуры распределения памяти при выполнении программы. Например, присваивание несуществуюгцему объекту значения через повисшую ссылку может изменить содержимое памяти, уже распределенной под другой объект данных совершенно другого типа (что нарушит безопасность структуры контроля типов).
Или такое присваивание может изменить вспомогательные данные (такие, как ссылку на список свободных блоков памяти), которые временно были помещены системой в тот блок памяти, на который указывала повисшая ссылка, Тем самым нарушится целостность системы управления ресурсами памяти. Наличие мусора — не такая серьезная проблема, тем не менее она причиняет некоторые неудобства. Объекты данных, которые стали мусором, занимают определенный объем памяти, который мог бы использоваться для других целей. Поскольку в любом компьютере, даже в больших машинах с оперативной памятью, составляюшей многие мегабайты, ее объем все же конечен, неограниченное накопление мусора может вызвать преждевременную остановку выполнения программы из-за нехватки памяти для выполнения операций.
Структуры управления ресурсами памяти, предназначенные для решения проблем с повисшими ссылками и мусором, обсуждаются в главе 10. 6.1.4. Объявления структур данных и контроль типов Основные понятия и проблемы, связанные с объявлениями структур данных и контролем нх типов, аяалогичны тем понятиям и проблемам, которые уже обсуждалнсь в связи с элементарными типами данных.
Тем не менее в случае со структурами данных все несколько усложняется, так как они являются более сложными и поэтому требуется определять большее количество атрибутов. Например, объявление языка С Поз[ А[203; расположенное в начале подпрограммы Р, определяет следующие атрибуты массива А: 1) тип данных — массив; 2) количество размерностей — 1; 3) количество компонентов — 20; 4) индексы представляют собой целые числа от 0 до 19; 5) тип данных каждого компонента — вегцественный. Объявление всех этих атрибутов позволяет выбрать последовательное представление для массива А, а также выбрать подходящую формулу доступа к любому компоненту А[[) массива А, которая может быть вычислена во время компиляции (см.
следующий раздел), хотя фактически массив А создается только при входе в подпрограмму Р во время выполнения программы. Если бы не было этого объявления, атрибуты массива А пришлось бы определять динамически во время выполнения программы, в результате чего представление массива в памяти и алгоритм доступа к его компонентам были бы гораздо менее эффективными. 246 Глава 6.
Инкапсуляция Проверка типов для структур данных — несколько более сложная процедура, так как приходится принимать во внимание операции выбора компонентов. Здесь возникают две основные проблемы. Е Существование выбранного компонента. Может возникнуть такая ситуация, что все аргументы для операции выборки имеют правильный тип, но искомый компонент попросту не существует в этой структуре данных, Например, операция индексации, которая используется при выборе компонента массива, может получить значение инпекса, выходящее за границы, лопустимые для этого массива (то есть будет получено неправильное 1-значение для компонента массива), Это не создаст проблемы с проверкой типов при условии, что операция выбора при этом не выполняется, а просто появляется сообщение об ошибке и генерируется исключение (например, ошибка диапазона индексации).
Однако если динамический контроль типов отключен в целях повышения эффективности и исключение не генерируется, то результат операции выбора почти всегда немедленно становится аргументом какой-либо другой операции. Если прн этом операция выбора выдала неверное 1-значение, то результат равносилен ошибке определения типов. Операция, которая использует результат операции выбора, получает в качестве аргумента неверное 1-зцачение (адрес блока памяти, в котором могут содержаться данные другого типа, выполняемый кол и т. д ). Операции выбора компонентов, которые используют формулу доступа для вычисления смещения искомого компонента в непрерывной последовательности блоков памяти, особенно подвержены этой ошибке; в этом случае во время выполнения программы часто требуется проверка существования компонента до вычисления формулы доступа, используемой для определения его точного 1-значения.
2. Тип выбранного компонента. Последовательность выбора может определять сложный путь доступа через структуру данных к искомому компоненту. Например,в языке С оператор А(2ПЗ] 11лК -~ Мея выбирает из записи содержимое компонента с именем 1~ее с помощью указателя, хранящегося в компоненте 11п1 другой записи, которая, в свою очередь, является элементом второй строки и третьего столбца массива А.
Для выполнения статического контроля типов должна существовать возможность определения во время компиляции типа компонента, выбираемого любым допустимым селектором подобного составного типа. Как было отмечено ранее, вообще нельзя заведомо предполагать, что выбранный компонент будет существовать в нужный момент при выполнении программы. Статический контроль типов может гарантировать только то, что, если компонент существует, его тип — правильный. 6.1.5.
Векторы и массивы Векторы и массивы — это наиболее распространенные типы структур данных, имеющиеся в языках программирования. Вектор — это структура данных, состоящая из фиксированного количества компонентов одного типа, организованных в виде 6.1. Структурированные типы данных 247 простой линейной последовательности. Компонент вектора выбирается путем указания индекса, который является целочисленным значением (или элементом перечисления), задающим местоположение компонента в этой последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
