Файл: Think likea programmer.pdf

118 Глава 4
Если у вас есть опыт работы со строками стандартной библи- отеки языка С/С++, вы сразу вспомните этот недостающий эле- мент, но если нет, то сможете быстро его вычислить. Давайте воспользуемся одной из наших техник решения задач, которая называется поиск аналогий . Возможно, стоит подумать о другой задаче с объектом неизвестной длины. В главе 2 мы оценивали корректность идентификационных номеров с произвольным ко- личеством цифр для решения задачи «Проверка контрольной сум- мы Луна». В этой задаче нам было заранее неизвестно, сколько цифр введет пользователь. В итоге мы использовали цикл while, который повторялся до тех пор, пока не был введен символ окон- чания строки.
К сожалению, в конце массива нет никакого символа окончания строки. Но что если мы вставим символ окончания строки в послед- ние элементы всех наших строковых массивов? Тогда мы сможем уз- нать размер массива так же, как до этого узнавали количество цифр в идентификационном коде. Единственный недостаток этого спо- соба заключается в том, что символ окончания строки мы сможем использовать только в качестве завершающего байта . Нельзя сказать, что это очень существенное ограничение, но для большей гибкости нужно выбрать символ, который точно никто не сможет поместить в массив. Таким образом, мы будем использовать ноль для завершения массива, так как ноль является кодом отсутствия символа в ASCII и других системах кодирования символов. Это тот самый метод, кото- рый применяется в стандартной библиотеке С/С++.
После того как мы разобрались с этим вопросом, давайте рас- смотрим подробнее, что же будет делать функция append с получен- ными данными. Как известно, функция получает два параметра: первый, arrayString
, является указателем на массив символов, хранящийся в куче. Второй параметр представляет собой перемен- ную типа char, которую нужно добавить в массив. Чтобы все ста- ло понятно, давайте напишем предварительный вариант функции append и протестируем его:
void append(
X arrayString& s, char c) {
}
void appendTester() {
Y arrayString a = new char[5];
Z a[0] = 't'; a[1] = 'e'; a[2] = 's'; a[3] = 't'; a[4] = 0;
[ append(a, '!');
\ cout << a << "\n";
}
Функция appendTester выделяет в куче память под нашу стро- ку
Y
. Обратите внимание, что длина массива составляет пять сим- волов, чтобы мы могли поместить туда четыре буквы слова test, а также нулевой завершающий байт
Z
. В следующей строке мы вы- зываем функцию append
[
, которая в этот момент является пустыш- кой. При ее написании я указал для параметра arrayString ссы-

Решение задач с указателями и динамической памятью 119
лочный тип (&)
X
, так как функция будет создавать новый массив в куче. Ведь весь смысл как раз и заключается в использовании дина- мического распределения памяти для создания нового массива при изменении размера строки. Таким образом, значение переменной a
при передаче в функцию отличается от того, которое возвраща- ет функция, так как возвращаемая переменная указывает на новый массив. Обратите внимание, что раз наши массивы используют применяемый в стандартной библиотеке нулевой завершающий байт, то мы можем передать массив по указателю a прямо в стан- дартный поток вывода, чтобы проверить значение
\
На рис. 4.4 можно увидеть представление работы функции с тестовым примером. Завершающие байты находятся на своих ме- стах и для простоты восприятия представлены как NULL. В части
(б) показано состояние после выполнения функции. Очевидно, что переменная s указывает на новый участок памяти. Предыду- щий массив окрашен серым, на этом рисунке я использую серый для освобожденных участков памяти. Изображение освобожден- ной памяти на рисунке напоминает нам фактически производить освобождение памяти.
Рис. 4.4. Обновленные и доработанные состояния до (а) и после (б) выполнения функции
append
Теперь мы можем записать функцию надлежащим образом со всеми подробностями.
void append(arrayString& s, char c) {
int oldLength = 0;
X while (s[oldLength] != 0) {
oldLength++;
}
Y arrayString newS = new char[oldLength + 2];
Z for (int i = 0; i < oldLength; i++) {
newS[i] = s[i];
}
[ newS[oldLength] = c;
\ newS[oldLength + 1] = 0;
] delete[] s;
^ s = newS;
}

120 Глава 4
В этом коде много чего происходит, так что давайте рассмотрим его шаг за шагом. В начале выполнения функции находится цикл, который находит завершающий байт массива и останавливается
X
После выполнения цикла значение переменной oldLength равно коли честву действительных символов в массиве (не считая нулевого завершающего байта). Мы выделяем в куче память для нового масси- ва в размере oldLength +2
Y
. Это одна из тех деталей, которую слож- но реализовать, если держать их все в голове, но легко сделать пра- вильно, если у вас есть рисунок. Рассматривая отображение нашего кода на рис. 4.5, мы видим, что значение переменной oldLength со- ставляет 4. И мы знаем, что переменная oldLength должна равнять- ся 4, так как в слове test четыре буквы, а также что новый массив на рис. 4.5 (б) содержит 6 символов, так как необходимо место для но- вого символа и для завершающего байта.
После выделения памяти для нового массива мы копируем в него все действительные символы из старого массива
Z
и добавляем в ко- нец новый символ
[
, а также ставим нулевой завершающий байт на его законное место в новом массиве
\
. И опять схема помогает нам мыслить ясно. Чтобы прояснить все еще больше, рис. 4.5 демонстри- рует, как было рассчитано значение переменной oldLength и на ка- кую позицию это значение указывает в новом массиве. С таким на- глядным напоминанием совсем не сложно расставить правильные значения в этих двух операциях присваивания.
Рис. 4.5. Взаимосвязь локальной переменной, параметров и выделяемой памяти до и после
применения функции
append
Последние три строки кода в функции append относятся к серо- му прямоугольнику в части (б). Чтобы избежать утечки памяти , мы должны удалить из кучи старый массив, на который все еще ссылает- ся параметр s
]
. И наконец, перед завершением вызова функции мы присваиваем параметру s указатель на новый, более длинный мас- сив
^
. К сожалению, одна из причин того, что утечки памяти так рас- пространены при программировании на языке С++, состоит в том, что, пока общий объем утечки памяти незначительный, ни програм-

Решение задач с указателями и динамической памятью 121
ма, ни система не демонстрируют никаких симптомов происходяще- го. Поэтому утечка может быть и не замечена на этапе тестирования.
Тем не менее мы как программисты должны тщательно подходить к вопросу времени существования выделенных участков памяти в куче. Если вы используете оператор new, то сразу думайте о том, где и когда нужно использовать соответствующий ему оператор delete.
Напомню, что при разработке этой функции нам очень помог- ла схема. Трудности программирования намного упрощаются с хо- рошей схемой, и я надеюсь, что все больше новых программистов будут составлять схемы, перед тем как писать код. Это возвращает нас назад к одному из основополагающих принципов решения за- дач: всегда составляйте план. Нарисовать хорошую схему для реше- ния задачи — это все равно что нанести на карту маршрут до пункта назначения, перед тем как отравиться в дальний путь. Это требует чуть больших усилий вначале, но в итоге позволит вам сэкономить намного больше сил и времени .
7-% *@
Все, что вам потребуется для составления схемы — это карандаш и бумага. Однако если у вас есть время, то я бы рекомендовал использовать специальную программу для составления схем. Существуют специализированные инструменты с набором шаблонов для целей программирования, но для начала вполне подойдет и самый простой векторный графический редактор (термин вектор означает, что програм- ма работает с линиями и кривыми, а не пикселами, как Photoshop). Я создал ил- люстрации к этой книге в бесплатной программе Inkscape. Составление схем на компьютере позволяет организовать их хранение в том же месте, где вы будете писать код, который эти схемы иллюстрируют. Кроме того, диаграммы должны быть аккуратными, чтобы можно было понять их спустя какое-то время. И наконец, на- много проще скопировать и изменить схему, нарисованную на компьютере как по- ступал я, когда подготавливал рис. 4.5 на основе рис. 4.4. А если вы хотите сделать какие-то быстрые пометки, то всегда можете распечатать себе экземпляр, чтобы покалякать на нем.
Давайте вернемся к функции append. Код выглядит солидно, но не стоит забывать, что мы написали этот код для типичного приме- ра. То есть нам не стоит задаваться и утверждать, что код подойдет для всех возможных случаев. В первую очередь, рекомендуется про- верить специальные случаи. Специальный случай в программирова- нии — это ситуация, в которой достоверные данные спровоцируют нормальный код выдать ошибочный результат.
Следует отметить, что эта проблема начинается с недостовер- ных данных, таких как , например, недопустимые значения. При на- писании кода для этой книги я предполагал, что все данные, пере- даваемые в программы и функции, будут корректными. Например, если программа ожидает несколько числовых значений, разделен- ных запятыми, то я предполагаю, что именно эти данные программа и получит, а не посторонние символы, нечисловые значения и так

122 Глава 4
далее. Подобное предположение необходимо, чтобы не раздувать размеры кода и исключить повторение одних и тех же проверок вво- димых данных из примера в пример. В реальной жизни, однако, мы должны принимать разумные меры предосторожности против не- корректного ввода данных. Это так называемая устойчивость. Устой-
чивая к ошибкам программа способна работать даже при вводе не- корректных данных. Например, такая программа может выдавать пользователю сообщение об ошибке вместо сбоя в работе.
Проверка на специальные случаи
Давайте опять обратимся к функции append и проведем проверку на специальные случаи. Другими словами, убедимся, что не возникнет никаких странных ситуаций с корректно введенными данными. Наи- более распространенными виновниками специальных случаев явля- ются крайние значения, которые больше или меньше допустимого диапазона. Что касается функции append, то здесь нет верхних огра- ничений по величине нашего строкового массива, но лимитирован минимальный размер. Если у строки нет допустимых значений, то она будет представлять собой массив из одного элемента (нулевого завершающего байта). Как и раньше, давайте для прояснения ситуа- ции нарисуем схему. Предположим, что мы добавили восклицатель- ный знак к нулевой строке, как это показано на рис. 4.6.
Рис. 4.6. Тестирование функции append в случае минимальной длины строки
Если вы взглянете на схему, то не заметите, что этот случай по- хож на специальный, но, чтобы убедиться, нам следует запустить нашу функцию с такими условиями. Давайте добавим несколько строк в код функции appendTester:
arrayString b = new char[1];
b[0] = 0;
append(b, '!');
cout << b << "\n";

Решение задач с указателями и динамической памятью 123
Здесь тоже все работает. Теперь, когда мы убедились, что функ- ция append работает корректно, полностью ли она нас устраивает?
Код кажется простейшим, и я не чувствую от него никакого «за- пашка», но кажется, что он немного длинноват для такой простой операции. Когда я обдумывал функцию concatenate, мне пришло в голову, что, как и функция append, функция concatenate нуждается в определении длины строкового массива, или, может быть, двух строковых массивов. Так как обе операции предполагают исполь- зование цикла, который будет определять нулевой завершающий байт, то мы можем поместить этот код в отдельную функцию. А по- том при необходимости сможем вызывать эту функцию из функ- ций append и concatenate. Давайте приступим к реализации этой задумки и модифицируем соответствующим образом функцию ap- pend
:
int length(arrayString s) {
Xint count = 0;
while (s[count] != 0) {
count++;
}
return count;
}
void append(arrayString& s, char c) {
Yint oldLength = length(s);
arrayString newS = new char[oldLength + 2];
for (int i = 0; i < oldLength; i++) {
newS[i] = s[i];
}
newS[oldLength] = c;
newS[oldLength + 1] = 0;
delete[] s;
s = newS;
}
Код в функции length
X
— это тот же самый код, с которого раньше начиналась функция append. А в самой функции append мы заменили этот фрагмент кода на вызов функции length
Y
. Функция length представляет собой вспомогательную функцию , то есть она инкапсулирует общую для нескольких других функций операцию.
Кроме того, она уменьшает объем кода, а избавление от излишков делает код более надежным и гибким. Это также способствует ре- шению нашей задачи, так как вспомогательные функции делят код на небольшие фрагменты, что упрощает возможность его повтор- ного использования.
Копирование динамически созданной строки
Теперь пришло время разобраться с функцией concatenate. Мы бу- дем пользоваться тем же подходом, что и при создании функции append
. Сначала мы напишем пустую заготовку для функции, чтобы определить параметры и их типы. Затем нарисуем схему тестового примера и в итоге напишем код, соответствующий схеме. Давайте взглянем на заготовку и пример для тестирования.

124 Глава 4
void concatenate(
XarrayString& s1, YarrayString s2) {
}
void concatenateTester() {
arrayString a = new char[5];
a[0] = 't'; a[1] = 'e'; a[2] = 's'; a[3] = 't'; a[4] = 0;
arrayString b = new char[4];
b[0] = 'b'; b[1] = 'e'; b[2] = 'd'; b[3] = 0;
concatenate(a, b);
}
Не забывайте, что в описании этой функции говорится, что сим- волы второй строки (второго параметра) добавляются в конец пер- вой строки. Таким образом, первый параметр функции будет ссылоч- ным
X
, по той же причине, что и первый параметр функции append.
Второй параметр
Y
, однако, не будет изменяться внутри функции, так что он будет передаваться по значению. Теперь перейдем к ус- ловиям для общего случая: мы конкатенируем строковые перемен- ные test и bed. Схема содержимого памяти до и после изображена на рис. 4.7.
Детали схемы нам уже знакомы из работы с функцией append. Для начала у нас есть два динамически созданных в куче массива, на ко- торые указывают параметры s1 и s2. Когда работа функции будет за- кончена, s1 будет указывать на новый массив, длина которого будет составлять девять символов. Массив, на который сначала указывал s1
, будет удален. Указатель s2 и его массив останутся без изменений.
В данный момент может показаться бессмысленным включение ука- зателя s2 и массива bed в нашу схему. Но если пытаться избежать оши- бок при написании кода, отслеживание того, что не меняется, так же важно, как и отслеживание того, что меняется. Здесь я также пронуме- ровал элементы старого и нового массивов, так как это нам очень при- годилось при написании функции append. Теперь, когда все разложено по полочкам, давайте приступим к написанию функции.
Рис. 4.7. Состояние памяти «до» (а) и «после» (б) вызова функции concatenate

Решение задач с указателями и динамической памятью 125
void concatenate(arrayString& s1, arrayString s2) {
Xint s1_OldLength = length(s1);
int s2_Length = length(s2);
int s1_NewLength = s1_OldLength + s2_Length;
YarrayString newS = new char[s1_NewLength + 1];
Zfor(int i = 0; i < s1_OldLength; i++) {
newS[i] = s1[i];
}
for(int i = 0; i < s2_Length; i++) {
newS[
[s1_OldLength + i] = s2[i];
}
\newS[s1_NewLength] = 0;
]delete[] s1;
^s1 = newS;
}
Для начала мы определяем длину обеих строк, которые будем скла- дывать
X
, а потом складываем эти величины и получаем длину объеди- ненной строки. Не забывайте, что при определении длины строк мы учитываем только действительные члены массива без нулевого завер- шающего байта. Так что, когда мы создаем в куче массив для хранения новой строки
Y
, мы выделяем память для количества элементов на один больше, чем объединенная длина двух массивов, чтобы добавить в конце нулевой завершающий байт. Затем мы копируем символы двух первоначальных строк в новую строковую переменную
Z
. Первый цикл совсем не сложный, но не забывайте о расчете индексов во вто- ром цикле
[
. Мы копируем элементы из начала массива s2 в середину массива newS. У нас уже был другой пример с переводом значений из одного диапазона в другой, который мы выполняли в главе 2. Глядя на номера элементов на моей схеме, я могу увидеть, какие величины я должен сложить вместе, чтобы правильно определить индекс эле- мента-цели. В оставшейся части функция добавляет нулевой заверша- ющий байт в конец новой строки
\
. Так же как и в функции append, мы удаляем массив, указателем на который является первый параметр
]
, и перенаправляем первый параметр на новый строковый массив
^
Этот код выглядит вполне рабочим, но, как и прежде, нужно убе- диться, что мы создали функцию, которая успешно работает не толь- ко для тестового примера, но и во всех остальных случаях. С большой вероятностью проблемы могут начаться в случае, когда один или оба параметра окажутся строками нулевой длины (содержащими толь- ко нулевой завершающий байт). Мы должны проверить этот случай, прежде чем двигаться дальше. Напомню, что при проверке коррект- ности кода, содержащего указатели, следует проверить именно сами указатели, а не только величины в куче, на которые они ссылаются.
Рассмотрим тестовый пример:
arrayString a = new char[5];
a[0] = 't'; a[1] = 'e'; a[2] = 's'; a[3] = 't'; a[4] = 0;
arrayString c = new char[1];
c[0] = 0;
concatenate(c, a);
cout << a << "\n" << c << "\n";
X cout << (void *) a << "\n" << (void *) c << "\n";