ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 435
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Решение задач с указателями и динамической памятью 113
ные участки, что снижает возможность ее использования. Суммарно в куче 85 свободных ячеек памяти, но, как показывает стрелка, са- мый длинный блок составляет всего 17 смежных ячеек. Другими сло- вами, если каждая ячейка размером 1 байт, то данная куча не может выполнить заявку на выделение памяти от оператора new, превыша- ющую 17 байтов, несмотря на то, что свободно 85 байтов.
Рис. 4.2. Фрагментированный пол, коробка, которая не помещается, фрагментированная
память
Объем памяти
При работе с памятью в первую очередь нужно разобраться с ограни- чениями ее использования. В современных компьютерных системах объемы памяти настолько велики, что можно принять ее за неограни- ченный ресурс, но на практике каждой программе выделяется ограни- ченный объем памяти. К тому же программистам стоит эффективнее работать с памятью, чтобы избежать общего замедления работы сис- темы. В многозадачных операционных системах (а это практически все современные операционные системы) каждый байт, впустую рас- траченный одной программой, приближает момент нехватки памяти для всех запущенных программ. В этом случае операционная систе- ма начинает процесс подкачки страницы, или свопинга — перемещение отдельных блоков памяти из оперативной памяти во вторичное хра- нилище. Подкачка страницы существенно замедляет и даже практи- чески останавливает работу системы. Такое состояние системы назы- вается пробуксовка .
Стоит отметить, что для того, чтобы общий объем памяти, ис- пользуемый программой, был минимальным, куча и стек должны быть максимально большими. Для доказательства давайте будем вы- делять по килобайту памяти из кучи, пока не начнутся проблемы:
const int intsPerKilobyte = 1024 / sizeof(int);
while (true) {
int *oneKilobyteArray = new int[intsPerKilobyte];
}
Сразу поясню, что этот ужасный код написан исключительно для наглядной демонстрации вопроса. Если вы решите попробо-
114 Глава 4
вать его на своем компьютере, то для безопасности сначала сохра- нитесь. А произойти должно следующее: программа замедлится и операционная система выведет сообщение о том, что невозмож- но обработать исключение bad_alloc . Это исключение возникает, если выполняется оператор new, а в куче нет свободного блока па- мяти подходящего размера, чтобы удовлетворить запрос. Нехватка памяти в куче называется переполнением кучи . В некоторых системах может произойти общее переполнение кучи, в то время как в дру- гих программа начнет пробуксовывать задолго до того, как будет сгенерировано исключение bad_alloc (оператор new смог вызвать падение моей системы, только когда я стал выделять по два гига- байта памяти).
Похожая ситуация происходит и со стеком вызовов. Каждый вы- зов функции выделяет определенный объем памяти в стеке для каж- дой записи активации, даже для функций без параметров и локаль- ных переменных:
X int count = 0;
void stackOver ow() {
Y count++;
Z stackOver ow();
}
int main()
{
[ stackOver ow();
return 0;
}
В этом коде введена глобальная переменная
X
, которая в боль- шинстве случаев — признак плохого стиля, но здесь мне необходи- ма величина, которая будет присутствовать во время всех рекурсив- ных вызовов. Так как эта переменная объявлена вне функции и здесь нет никаких параметров и локальных переменных, то для нее не создается запись активации и не выделяется память. Функция увели- чивает переменную count
Y
на единицу и производит рекурсивный вызов
Z
. Рекурсия будет подробно рассмотрена в главе 6, но исполь- зуется здесь для того, чтобы произвести максимальное количество вызовов функции. Запись активации функции остается в стеке, пока функция не прекратит свою работу. Таким образом, когда происхо- дит первый вызов функции stackOver ow из функции main
[
, запись активации попадает в стек и не может быть удалена, пока не закон- чится первый вызов функции. А этого никогда не случится, так как функция осуществит второй вызов stackOver ow, и новая запись ак- тивации попадет в стек, а потом будет осуществлен третий вызов и так далее. Эти записи активации будут добавляться в стек, пока он не переполнится. В моей системе программа прекратила работу, когда значение переменной count достигло около 4900. Моя среда разра- ботки Visual Studio выделяет под стек 1 Мб, следовательно, каждый вызов функции без локальных переменных и параметров создает за- пись активации размером около 200 байтов.
Решение задач с указателями и динамической памятью 115
Время существования переменной
Временной временем существования промежуток между выделением и высвобождением памяти называется переменной. В случае с перемен- ными, хранящимися в стеке — а это параметры и локальные перемен- ные, — время существования определяется косвенно. Переменная по- является при вызове функции и исчезает, когда функция возвращает управление. В случае с переменными, хранящимися в куче — а это пе- ременные, память под которые выделяется динамически с помощью оператора new, — мы можем напрямую задавать срок существования.
Управление временем существования переменной — это бич каждого программиста С++. Наиболее очевидная проблема — это утечка памяти, ситуация, когда память в куче выделяется, но никогда не освобождает- ся и недоступна с помощью указателей. Ниже показан простой пример:
X int *intPtr = new int;
Y intPtr = NULL;
Мы объявляем указатель на переменную типа int
X
и инициали- зируем ее путем выделения памяти под переменную типа int в куче.
Во второй строке мы присваиваем указателю значение NULL
Y
(это, по сути, псевдоним нуля). Но переменная типа int, память под ко- торую была выделена с помощью оператора new, все еще существу- ет. И находится она, одинокая и всеми забытая, на своем месте в куче, ожидая удаления, которое может и вовсе не произойти. Мы не можем освободить память, выделенную под int, так как для вызова оператора delete необходим указатель, которого у нас больше нет.
Если мы попытаемся продолжить вышеприведенный код командой delete intPtr
, то получим ошибку, так как указатель нулевой.
Иногда вместо памяти, которую невозможно высвободить, мы по- лучаем обратную проблему: пытаемся освободить память повторно, что вызывает ошибку времени выполнения. Может показаться, что эта проблема легко разрешима: следует просто не вызывать опера- тор delete дважды на одну и ту же переменную. Но не все так просто, ведь может оказаться, что множество переменных указывают на одну ячейку памяти. Если это действительно так и мы вызываем оператор delete для любой из этих переменных, то фактически мы очищаем память для всех переменных. Указатели, которым неявно присваива- ется значение NULL, называются висячими , а попытка применить к ним оператор delete вызывает ошибку времени выполнения.
Решение задач с указателями
Вот и настал момент, когда вы уже достаточно готовы к решению за- дач. Поэтому давайте рассмотрим несколько и попробуем применить указатели и динамическое распределение памяти для их решения.
Для начала займемся динамическими массивами, на примере кото- рых научимся отслеживать память в куче с помощью определенных
116 Глава 4
манипуляций. А потом мы проверим себя в деле с настоящими дина- мическими структурами.
Строка переменной длины
В первой задаче мы создадим функции для работы с переменными строкового типа . Здесь мы используем термин «строка» в его самом широком смысле — произвольной последовательности символов.
Полагаю, нам необходимо обеспечить три функции нашей строки.
: & " " $ #
Напишите, используя кучу, реализацию трех основных функций строковых переменных:
a e d
Функция получает в качестве параметров строку и символ и добавляет символ к конец строки.
o ate ate
Функция получает две строки и добавляет символы второй строки к первой.
haratert
Функция получает строку и число и возвращает символ, находящий- ся на соответствующей числу позиции (нумерация символов начинается с нуля).
При написании кода учитывайте, что функция characterAt будет применяться часто, в то время как две другие функции — достаточно редко. Частота вызовов отразит отно- сительную эффективность операций.
В этой задаче требуется таким образом реализовать строко- вую переменную , чтобы максимально быстро выполнять функцию characterAt
, то есть обеспечить кратчайший путь достижения того или иного символа. Как вы, возможно, помните из темы предыдущей главы, именно массивы наилучшим образом обеспечивают произ- вольный доступ к данным. Давайте решим эту задачу, используя мас- сив элементов типа char. Функции append и concatenate изменяют длину строки, из-за чего мы столкнемся со всеми теми проблемами, которые обсудили выше. Так как в условиях задачи не задан встроен- ный ограничитель длины строки, мы не можем объявить огромный массив и надеяться на лучшее. Вместо этого нам придется изменять размер массива во время выполнения программы.
Для начала давайте создадим псевдоним для нашего строкового типа с помощью спецификатора typedef .
Мы знаем, что будем созда- вать динамические массивы, так что нам необходимо объявить стро- ковый тип указателем на char. typedef char * arrayString;
Сделав это, мы можем перейти к реализации функций. Руковод- ствуясь принципом начинать с самого простого и понятного, мы мо- жем быстро создать функцию characterAt.
char characterAt(arrayString s, int position) {
X return s[position];
}
Решение задач с указателями и динамической памятью
1 ... 10 11 12 13 14 15 16 17 ... 34
117
Напомню из темы третьей главы, что если указатель указывает на массив, то мы можем получить доступ к элементам этого масси- ва с помощью обычной индексной записи
X
. Замечу, однако, что не- приятности могут начаться в том случае, если элемента с номером position больше нет в массиве s, так как этот код перекладывает от- ветственность за проверку второго параметра на вызывающего. Мы рассмотрим альтернативные решения в упражнениях в конце главы.
А сейчас давайте перейдем к реализации функции append
В общих чертах нам известно, что должна делать эта функция, но, чтобы ра- зобраться в деталях, давайте рассмотрим пример. Этот прием я на- зываю решением с помощью типичного примера.
Начнем с необычного примера передачи данных в функцию или программу. Запишите все детали этого ввода, а также вывода. Тогда вы сможете написать код для типичной ситуации, а потом изменить его под свой пример, дважды перепроверяя каждый шаг, чтобы гаран- тировать достижение желаемого конечного состояния. Эта техника очень хорошо помогает при работе с указателями и динамическим распределением памяти, так как многое из происходящего в програм- ме неочевидно на первый взгляд. Рассмотрение примера на бумаге помогает отслеживать все изменения значений в памяти, причем не только представленные в виде переменных, но и хранящиеся в куче.
Полагаю, что нам стоит начать со строковой переменной test, представляющей собой хранящийся в куче массив символьных пе- ременных t, e, s и t, который мы хотим дополнить восклицатель- ным знаком при помощи функции append. На рис. 4.3 можно уви- деть состояние памяти «до» (а) и «после» (б) этой операции. На схеме слева от вертикальной пунктирной линии изображен стек
(локальные переменные или параметры), а справа изображен уча- сток памяти в куче, который был выделен динамически с помощью оператора new.
Рис. 4.3. Состояние памяти «до» (а) и «после» (б) вызова функции append.
Глядя на рисунок, я, кажется, уже предвижу возможные пробле- мы при работе нашей функции. Учитывая наш способ реализации строки, функция создаст новый массив, на один элемент длиннее предыдущего, и скопирует все символы из старого массива в новый.