Файл: Think likea programmer.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.10.2023

Просмотров: 438

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

158 Глава 5связным списком, это исходный головной указатель, имеющий зна- чение NULL. Здесь это определенно вызовет проблему, поскольку мы не проверяем это и код вызовет сбой, если мы попытаемся разыме- новать указатель loopPtr после входа в цикл. Кроме того, мы должны рассмотреть возможность, что идентификатор, переданный клиент- ским кодом, вообще не соответствует никаким записям в коллекции. В этом случае, даже если _listHead не NULL, loopPtr в конце концов станет NULL, когда мы достигнем конца списка. Таким образом, основная идея состоит в том, что мы должны остановить цикл, если значение loopPtr становится NULL. Это не сложно, но что мы вернем в такой ситуации? Очевидно, мы не можем вернуть loopPtr->studentData, поскольку loopPtr будет NULL. Вме- сто этого мы можем создать и вернуть фиктивную запись student-Record с очевидно некорректными значениями. studentRecord studentCollection::recordWithNumber(int idNum) {studentNode * loopPtr = _listHead;while (XloopPtr != NULL && loopPtr->studentData.studentID() != idNum) {loopPtr = loopPtr->next;}if (YloopPtr == NULL) {Z studentRecord dummyRecord( –1, –1, "");return dummyRecord;} else {return loopPtr->studentData;}}В этой версии метода, если цикл закончен, а указатель цикла со- держит значение NULL Y, мы создаем фиктивную запись с пустой строкой вместо фамилии студента и значениями –1 для его оценки и идентификатора Z и возвращаем эту запись. Возвращаясь к циклу, мы проверяем, равен ли NULL указатель loopPtr, что может произойти, если список пуст либо мы безуспешно полностью его просмотрели. Обратим внимание, что выражение условия цикла X — составное вы- ражение с условием loopPtr != NULL, идущим первым. Именно так и должно быть. Язык C++ использует для оценки составных логических выражений механизм, известный как сокращенные вычисления . Проще говоря, правая часть составного логического выражения не рассма- тривается, если значение всего выражения уже известно. Поскольку && означает логическое и, то если левая часть выражения && оказыва- ется ложной, все выражение также оказывается ложью, независимо от значения правой части. Для повышения эффективности, C++ ис- пользует этот факт, опуская расчет правой части выражения && , если левая часть оказывается ложной (для || или логического или правая часть по той же причине не рассчитывается, когда левая часть истин- на). Следовательно, когда loopPtr равен NULL, выражение loopPtr != NULL ложно, и правая часть выражения && не рассчитывается. Без со- кращенных вычислений правая часть рассчитывалась бы и указатель на NULL разыменовывался бы, вызывая сбой программы. Решение задач с классами 159Эта реализация позволяет избежать потенциальной поломки, ха- рактерной для первой версии, однако она оказывает слишком много доверия клиентскому коду. То есть функция, вызывающая этот метод, должна проверить вернувшуюся обратно запись studentRecord и до выполнения дальнейших операций убедиться, что она не фиктивная. Если вы похожи на меня, то вам должно быть немного не по себе . .%4B/Есть еще один способ. C++, как и многие другие языки программирования, пред-лагает механизм, известный как исключения, позволяющий методу или глобальной функции недвусмысленно сообщить об ошибке туда, откуда она была вызвана. Это сделано для ситуации, которая сложилась в этом методе, когда нет хорошего отве-та на вопрос, что возвращать, если ввод был некорректным. Исключения сложнее, чем мы можем позволить себе рассматривать сейчас, и, к сожалению, реализация исключений в C++ не решает проблему доверия, описанную в предыдущем абзаце.Перегруппировка спискаМетод removeRecord похож на recordWithNumber в той, что мы должны пройти список для нахождения узла, который необходимо удалить. Однако есть задачи сверх этого. Удаление узла из списка требует вни- мательности, поскольку остальные узлы должны остаться связным списком. Проще всего зашить сделанную нами дырочку соединени- ем узла, который шел перед удаленным, с тем, который шел следом за ним. Нам не нужно набрасывать функцию, потому что у нас уже есть прототип функции в объявлении класса, поэтому перей дем к тестам.studentCollection s;studentRecord stu3(84, 1152, "Sue");studentRecord stu2(75, 4875, "Ed");studentRecord stu1(98, 2938, "Todd");s.addRecord(stu3);s.addRecord(stu2);s.addRecord(stu1);X s.removeRecord(4875) Мы создали объект s класса studentCollection, а также три объ- екта класса studentRecord, каждый из которых был добавлен в кол- лекцию. Обратите внимание, что мы могли бы использовать одну и ту же запись, меняя значения между вызовами addRecord, но не стали этого делать для упрощения тестового кода. Последняя строка в те- сте вызывает метод removeRecord X, который в данном случае удалит вторую запись, то есть запись для студента по имени «Ed». Используя тот же стиль схем указателей, что и в главе 4, проиллюстрируем на рис. 5.1 состояние памяти «до» и «после» этого вызова.На рис. 5.1 (а) мы видим связный список, созданный нашим тесто- вым кодом. Обратите внимание, что, поскольку мы используем класс, наши соглашения о схемах слегка искажены. В левой части рисунка 160 Глава 5изображен стек/куча, в котором находятся _listHead, являющийся приватным полем внутри объекта s класса studentCollection, и idNum, являющийся параметром метода removeRecord. В правой части рисун- ка изображен сам список в куче. Помните, что addRecord размещает новую запись в начало списка, поэтому записи расположены в обрат- ном порядке по сравнению с тем, как они добавлялись в тестовом коде. Идентификатор среднего узла, «Ed» совпадает с параметром 4875, поэтому он должен быть удален из списка. Рис. 5.1 (б) показыва- ет результат вызова метода. Первый узел списка, «Todd», теперь ука- зывает на узел, который ранее был в списке третьим, то есть на «Sue». Узел «Ed» больше не связан с большим списком и удален. Рис. 5.1. Ситуация «до» и «после» вызова метода removeRecord в тестовом примере Теперь, зная, какого результата мы хотим добиться, начнем пи- сать код. Поскольку мы знаем, что нам надо найти узел с соответ- ствующим идентификатором, мы могли бы начать с цикла while из метода recordWithNumber. По окончанию это цикла указатель будет указывать на узел, который надо удалить. К сожалению, нам надо кое-что еще, чтобы закончить удаление. Посмотрите на рис. 5.1. Что- бы закрыть дыру и восстановить связный список, мы должны изме- нить поле next узла «Todd». Если все, что у нас есть, это указатель на узел «Ed», способа указать на «Todd» не существует, потому что каждый узел в связном списке указывает на своего последователя, а не предшественника. (Из-за подобной ситуации некоторые связные списки связывают в обоих направлениях, такие списки называются Решение задач с классами 161двойные связные списки , но нужда в них возникает редко.) Таким об- разом, в дополнение к указателю на удаляемый узел (который назы- вается loopPtr, если мы применим код предыдущей функции), нам необходим указатель на предыдущий узел: давайте назовем такой указатель trailing. Рис. 5.2 демонстрирует эту концепции примени- мо к нашему примеру.Рис. 5.2. Указатели, необходимые для удаления узла с номером idNumC указателями loopPtr ссылающимся на удаляемый узел и trail- ing, ссылающимся на предыдущий узел, мы можем удалить желае- мый узел и сохранить список.void studentCollection::removeRecord(int idNum) {studentNode * loopPtr = _listHead;X studentNode * trailing = NULL;while (loopPtr != NULL && loopPtr->studentData.studentID() != idNum) {Ytrailing = loopPtr;loopPtr = loopPtr->next;}Z if (loopPtr == NULL) return;[ trailing->next = loopPtr->next;\ delete loopPtr;}Первая часть этой функции похожа на метод recordWithNumber, с тем исключением, что мы объявили указатель trailing X и внутри цикла присвоили ему старое значение loopPtr Y до перехода loopPtr к следующему узлу. Таким образом, указатель trailing всегда нахо- дится на один узел позади loopPtr. Благодаря нашей работе с пре- дыдущей функцией мы уже знаем про специальный случай. Поэтому, когда цикл закончится, мы проверяем, не равен ли loopPtr значе- нию NULL. Если равен, это означает, что мы не нашли узел с заданным идентификатором и немедленно возвращаемся Z. Я называю выра- жение return в середине функции «смываться». Некоторые програм- мисты возражают против этого, потому что функцию с несколькими точками выхода тяжело читать. Однако альтернативный вариант в этом случае еще один уровень вложения для инструкции if, которое идет следом, так что я лучше смоюсь. Определив, что удаляемый узел существует, пора удалить его. На диаграмме видео, что необходимо установить, чтобы поле next узла 162 Глава 5trailing указывало на узел, на который в настоящий момент указы- вает поле next узла loopPtr [. Затем мы можем безопасно удалить узел, на который указывает loopPtr \Этот код работает для нашего тестового примера, но, как всег- да, необходимо проверить его на возможных специальных случаях . Мы уже разобрались с возможностью, что номер idNum отсутствует в записях нашей коллекции, но нет ли еще какой-нибудь проблемы? Посмотрим на пример. Изменится ли что-нибудь, если мы попробу- ем удалить первый или третий узел вместо среднего? Тестирование показывает отсутствие проблем при удалении третьего (последнего) узла. Однако удаление первого узла и в самом деле вызывает труд- ности из-за того, что в этом случае отсутствует предыдущий узел, на который должен указывать trailing. Для этого мы должны мани- пулировать указателем _listHead. Рис. 5.3 иллюстрирует ситуацию, сложившуюся по окончании цикла while. Рис. 5.3. Положение до удаления первого узла в спискеВ этой ситуации нам нужно перенаправить _listHead на бывший второй узел в списке, то есть на узел «Ed». Давайте перепишем наш метод, чтобы решить данную проблему. void studentCollection::removeRecord(int idNum) {studentNode * loopPtr = _listHead;studentNode * trailing = NULL;while (loopPtr != NULL && loopPtr->studentData.studentID() != idNum) {trailing = loopPtr;loopPtr = loopPtr->next;}if (loopPtr == NULL) return;X if (trailing == NULL) {Y _listHead = _listHead–>next;} else {trailing->next = loopPtr->next;}delete loopPtr;}Как видите, как проверка условия X, так и код, решающий про- блему Y, просты, поскольку мы тщательно проанализировали ситуа- цию, прежде чем писать его. Решение задач с классами 163Деструктор Реализовав эти три метода, мы можем подумать, что класс stu- dentCollection готов. Однако это не так. Первое, чего не хватает нашему классу, это деструктор. Это специальный метод, вызывае- мый, когда объект выходит из области видимости (когда функция, объявившая этот объект, закончила работу). Если в классе отсут- ствуют динамические данные, обычно деструктор не нужен. Одна- ко если такие данные присутствуют, без деструктора не обойтись. Помните, для того, чтобы не допустить утечек памяти, мы долж- ны применить ключевое слово delete для всех объектов, которым была выделена память с помощью ключевого слова new. Если объ- ект нашего класса studentCollection содержит три узла, необхо- димо освободить память, которую занимает каждый из них. К сча- стью, это несложно. Нам необходимо пройти по нашему связному списку, удаляя узлы. Однако вместо того, чтобы делать это непо- средственно, давайте напишем служебный метод, удаляющий все узлы в studentList. В приватной секции нашего класса добавим объявление:void deleteList(studentList &listPtr);Код для этого метода будет выглядеть так:void studentCollection::deleteList(studentList &listPtr) {while (listPtr != NULL) {X studentNode * temp = listPtr;Y listPtr = listPtr->next;Z delete temp;}}Во время обхода указатель на текущий узел копируется во вре- менную переменную X, передвигается к следующему узлу Y, а за- тем удаляется узел, на который указывает временная переменная ZС помощью этого кода мы можем написать деструктор очень просто. Прежде всего, добавим деструктор в публичную секцию объявления нашего класса:studentCollection();Обратите внимание, что, как и у конструктора, имя деструктора совпадает с названием класса и в нем отсутствует возвращаемый тип. Тильда перед именем позволяет отличить деструктор от конструкто- ра. Реализация будет выглядеть так:studentCollection::studentCollection() {deleteList(_listHead);}Код в этом методе прост, однако очень важно протестировать де- структор. Хотя плохо написанный деструктор и может вызвать сбой вашей программы, большинство проблем с деструктором вызывают 164 Глава 5не ошибку программы, но утечки памяти или, что хуже, необъясни- мое поведение программы. Следовательно, важно протестировать деструктор с помощью отладчика среды разработки, так чтобы вы могли видеть, действительно ли деструктор вызывает delete для каждого узла.Глубокое копирование Осталась еще одна серьезная проблема. В главе 4 мы кратко обсу- дили концепцию перекрестных связей , когда две переменных типа указатель имеют одно и то же значение. Даже если это разные пе- ременные, они указывают на одну и ту же структуру данных; следо- вательно, изменение структуры одной переменной изменяет обе. Эта проблема часто всплывает в классах, включающих динамиче- ски распределенную память. Чтобы увидеть, почему это проблема, рассмотрим следующий элементарный код на C++:int x = 10;int y = 15;x = y;X x = 5;Предположим, я спросил бы вас, какое влияние последнее выра- жение X оказывает на переменную y. Вы, вероятно, удивились бы не оговорился ли я. Последнее выражение не оказывает совсем никако- го эффекта на y, только на x. А теперь посмотрите на это:studentCollection s1;studentCollection s2;studentRecord r1(85, 99837, "John");s2.addRecord(r1);studentRecord r2(77, 4765, "Elsie");s2.addRecord(r2);X s1 = s2;Y s2.removeRecord(99837) Предположим, я спрошу вас, какое влияние окажет последнее вы- ражение Y на s1. К сожалению, влияние действительно будет. Хотя s1 и s2 — два разных объекта, они отныне не полностью отдельные объекты. По умолчанию, когда один объект приравнен к другому, как мы сейчас приравняли объекты s1 и s2 X, язык C++ производит то, что известно как поверхностное копирование . При поверхностном ко- пировании каждое поле класса одного объекта присваивается друго- му. Так если, _listHead — наше единственное поле класса, публично, s2 = s1 будет аналогично s1._listHead = s2._listHead. Получае- тся, что поле _listHead обоих объектов указывает на одно и то же место в памяти: узел для «Elsie», который указывает на другой узел, а именно на узел «John». Поэтому после удаления узла «John», он уда- ляется из двух списков, поскольку на самом деле существует только один список. Рис. 5.4 иллюстрирует положение, сложившееся к кон- цу данного кода. Решение задач с классами 165Рис. 5.4. Результаты поверхностного копирования при перекрестных связях; удаление узла «John» из одного списка удаляет из обоих Однако все может быть еще хуже. Что, если последняя строка кода удалит первую запись — узел «Elsie»? В этом случае указатель _listHead объекта s2 станет указывать на узел «John», а узел «Elsie» будет удален. Однако указатель _listHead объекта s1 по-прежнему будет указывать на удаленный узел «Elsie», то есть возникнет опасная висячая ссылка , как показано на рис. 5.5.Рис. 5.5. Удаление из s2 приводит к висящей ссылке в s1Для решения этой проблемы применяют глубокое копирование, то есть не только копирование указателя на структуру, но копирова- ние всей структуры. В нашем случае это означает копирование всех узлов списка. Тем самым происходит истинное копирование. Как и ранее, давайте начнем с приватных служебных методов, то есть в нашем случае с метода, копирующего studentList. Объявление в приватной секции класса выглядит примерно так:studentList copiedList(const studentList original);Как и ранее, я выбрал существительное для названия метода, возвра щающего значение. Реализация метода выглядит так:X studentCollection::studentList studentCollection::copiedList(const studentList original) {Y if (original == NULL) {return NULL;}studentList newList = new studentNode;Z newList->studentData = original->studentData;[ studentNode * oldLoopPtr = original->next;\ studentNode * newLoopPtr = newList;while (oldLoopPtr != NULL) { 166 Глава 5] newLoopPtr->next = new studentNode;newLoopPtr = newLoopPtr->next;newLoopPtr->studentData = oldLoopPtr->studentData;oldLoopPtr = oldLoopPtr->next;}^ newLoopPtr->next = NULL;_ return newList;}В этом методе происходит много всего, поэтому давайте будем раз- бираться постепенно. Прежде всего, обратим внимание, что, опреде- ляя тип возвращаемого значения, мы должны указать в префиксе имя класса X. В противном случае компилятор не поймет, о каком типе мы говорим. (Внутри метода это необязательно, поскольку компилятор уже знает, частью какого класса является метод – немного запутанно!) Мы проверяем, не пуст ли входящий список. Если он пуст, смываем- ся Y. Теперь, зная, что у нас есть список для копирования, копируем данные первого узла до начала цикла Z, поскольку для этого узла нам необходимо изменить указатель на начало нового списка.Затем мы устанавливаем два указателя для прохода по списку. Ука- затель oldLoopPtr [ проходит через пришедший список; он всегда бу- дет указывать на узел, который мы собираемся копировать. Указатель newLoopPtr\ проходит через новый, скопированный, список и всегда указывает на последний созданный узел, то есть узел, до которого мы будем добавлять следующий узел. Как и в методе removeRecord нам ну- жен здесь хвостовой указатель. В цикле ] мы создаем новый узел, пе- редвигаем newLoopPtr, чтобы он указывал на него, копируем данные из старого узла в новый и передвигаем указатель oldLoopPtr. После цикла мы завершаем новый список, присваивая значение NULL полю next по- следнего узла ^ и возвращаем (return) указатель на новый список _Как же этот служебный метод решает обозначенную выше пробле- му? Сам по себе никак. Но, добавив этот код, мы можем перегрузить оператор присваивания. Перегрузка операторов — особенность языка C++, позволяющая изменять действия, производимые встроенными операторами над определенными типами данных. В нашем случае мы хотим перегрузить оператор присваивания (=) так, чтобы вместо уста- новленного по умолчанию поверхностного копирования, он вызывал наш метод copiedList для выполнения глубокого копирования. В пуб- личной секции класса добавим следующее:XstudentCollection& Yoperator=(Zconst studentCollection & [rhs);Перегружаемый оператор определяется названием метода с ис- пользованием ключевого слова operator, за которым идет оператор, который мы хотим перегрузить Y. Имя выбранное мной для параме- тра (rhs [) обычный выбор для перегрузки операторов, поскольку это сокращение от словосочетания «правая сторона» (right-hand side). Это помогает программистам упрощать себе жизнь. Так, в присвое- нии, о котором идет речь s2 = s1, объект s1 будет правой стороной оператора присваивания, а s2 — левой стороной . На правую часть мы Решение задач с классами1   ...   16   17   18   19   20   21   22   23   ...   34

167ссылаемся через параметр, а на левую — непосредственно через поле класса, так же как и при любом другом методе класса. Итак, наша зада- ча состоит в создании списка, на который будет указывать _listHead и который будет являться копией списка, на который указывает _lis- tHead объекта rhs. Таким образом, при вызове s2 = s1 будет создан объект s2 как истинная копия объекта s1. Тип параметра — это постоянная ссылка на наш класс Z. Тип воз- вращаемого значения — это всегда ссылка на класс X. Скоро вы увиди- те, почему параметр — это ссылка. Вас, возможно, удивляет, почему метод возвращает все подряд, начиная с того, что мы изменяем поле класса непосредственно в методе. Это происходит из-за того, что язык C++ позволяет присвоение по цепочке, например s3 = s2 = s1, в котором возвращаемое значение первого присвоения становится па- раметром следующего.Теперь, когда синтаксис понятен, код оператора присваивания становится вполне очевидным:studentCollection& studentCollection::operator=(const studentCollection &rhs) {X if (this != &rhs) {Y deleteList(_listHead);Z _listHead = copiedList(rhs._listHead);}[ return * this;}Чтобы избежать утечки памяти, мы сначала должны удалить все узлы из левостороннего списка Y. (Именно для этой цели мы отдель- но написали вспомогательный метод deleteList, а не включили его код непосредственно в деструктор.) Удалив предыдущий левосторон- ний список, мы копируем правосторонний список, используя наш другой вспомогательный метод Z. Однако до выполнения этих шагов мы проверяем, что объект с правовой стороны отличается от объекта с левой (то есть, это не что-то подобное s1 = s2) проверяя, отлича- ются ли указатели X. Если указатели одинаковые, нет необходимости что-то делать, при этом это не вопрос эффективности. Если мы вы- полним глубокое копирование для одинаковых указателей, когда мы будем удалять узлы в левостороннем списке, мы также будем удалять узлы и в правостороннем. Наконец, мы возвращаем указатель на лево- сторонний объект [; это случится независимо от того, действительно ли скопировали мы что-нибудь или нет, потому что, хотя выражение, подобное s3 = s2 = s1, выглядит странным, мы хотим, чтобы оно рабо тало, если кто-нибудь попытается его выполнить.Сделав служебный метод для копирования списка, мы должны создать и копирующий конструктор . Это конструктор, принимающий другой объект того же класса как объект. Копирующий конструктор вызывается явно, когда нам надо создать дубликат существующего списка studentCollection, но может вызываться и неявно, если объ- ект этого класса передается как параметр по значению в функцию. Из-за этого вы должны предусмотреть передачу объекта по ссылке 168 Глава 5с ключевым словом const вместо передачи по значению, за исклю- чением тех случаев, когда функция, получающая объект, должна из- менить его копию. В противном случае ваш код будет делать много ненужной работы. Например, рассмотрим коллекцию из 10 000 за- писей о студентах. Коллекция может быть передана по ссылке одним указателем. В противном случае копирующий конструктор будет вы- зываться каждый раз во время длительного прохода по коллекции и распределять память 10 000 раз. Затем для этих копий в конце рабо- ты функции будет вызван деструктор с очередным долгим проходом по коллекции высвобождением памяти 10 000 раз. Вот поэтому пра- восторонний параметр перегрузки оператора присваивания исполь- зует параметр по ссылке с ключевым словом const. Для добавления копирующего конструктора в наш класс, доба- вим прежде его объявление в публичной секции объявления нашего класса.studentCollection(const studentCollection &original);Как и во всех конструкторах, здесь нет типа возвращаемого зна- чения. И, как и в случае перегрузки оператора присваивания, пере- даваемый параметр — это ссылка на наш класс с ключевым словом const. Поскольку мы уже создали служебный метод, реализация бу- дет простой. studentCollection::studentCollection(const studentCollection &original) {_listHead = copiedList(original._listHead);}Теперь мы можем выполнить подобное объявление:studentCollection s2(s1);Это объявление создает s2 и копирует туда все узлы s1. Общий обзор классов с динамической памятьюМы сделали многое в этом классе, завершив методы, указанные в ус- ловиях задачи, а теперь давайте взглянем, что у нас получилось. Вот так выглядит объявление нашего класса.class studentCollection {private:struct studentNode {studentRecord studentData;studentNode * next;};public:studentCollection();studentCollection();studentCollection(const studentCollection &original);studentCollection& operator=(const studentCollection &rhs);void addRecord(studentRecord newStudent);studentRecord recordWithNumber(int idNum);void removeRecord(int idNum); Решение задач с классами 169private:typedef studentNode * studentList;studentList _listHead;void deleteList(studentList &listPtr);studentList copiedList(const studentList original);};Данный урок состоит в том, что при создании классов с динами- ческой памятью необходимо добавлять новые части. В дополнении к сущностям базового фреймворка класса — приватным данным, конструктору и методам отправления данных в объект и получе- ния их оттуда — мы должны добавить методы, работающие с выде- лением и высвобождением динамической памяти. Как минимум мы должны добавить конструктор и деструктор копирования, а также перегрузить оператор присваивания, если есть вероятность, что он кому-нибудь понадобится. Создание этих дополнительных мето- дов часто облегчается созданием служебных методов копирования или удаления динамических структур данных. Кажется, что это большая работа. И это действительно мо- жет быть так. Но важно понимать, что со всем, что вы добавите в класс, вам так или иначе придется разбираться. Другими словами, даже если у нас нет класса для коллекции записей о студентах, ос- нованной на связном списке, мы все равно должны удалять узлы в списке после прохода по ним. Нам все равно придется думать о перекрестных связях, все равно придется проходить сквозь спи- сок и копировать узел за узлом, если нам нужна истинная копия исходного списка и так далее. Размещение всего в класс требует немного больше начальной подготовки, но как только все зара- ботает, клиентский код может не задумываться обо всех деталях, связанных с распределением памяти. Кроме того, инкапсуляции и сокрытие существенно облегчают работу со структурами дина- мических данных.Ошибки, которых следует избегатьМы поговорили о том, как создать хороший класс в языке C++, да- вайте теперь обсудим несколько подводных камней, которые следу- ет избегать.Фальшивый класс Как я уже говорил в начале этой главы, я считаю C++ отличным язы- ком для изучения объектно ориентированного программирования, поскольку это гибридный язык, включающий как процедурную, так и объектно ориентированную парадигму. В этом случае создание класса всегда является выбором программиста. В языках, подобных Java, никогда не стоит вопрос: «Надо ли мне делать класс?» Вместо него возникает вопрос: «Как мне поместить это все в класс?» Тре- бование поместить все в класс приводит к появлению того, что я 170 Глава 5называю фальшивым классом, то есть классом без последовательного проектирования, который корректен синтаксически, но не имеет смысла. Слово класс, как его используют программисты, соответ- ствует смыслу английского слова, означающего группу вещей с об- щими атрибутами, и хороший класс языка C++ соответствует этому определению.Фальшивый класс может быть создан по нескольким причинам. Например, программист хочет использовать глобальные перемен- ные, но не по обоснованным причинам (такие причины редки, но все-таки существуют), а из-за лени — чтобы избегать передачи пара- метров от функции к функции. При этом если программист пони- мает, что широкое использование глобальных переменных это при- знак плохого стиля, он или она полагает, что нашел лазейку. Все или большинство функций программы сваливают в класс, и теперь пере- менные, которые были бы глобальными, становятся полями этого класса. Функция main такой программы создает объект этого фаль- шивого класса и вызывает какой-то «главный» метод в классе. Тех- нически программа не использует глобальные переменные, но фаль- шивый класс означает, что этой программе присущи все недостатки программы с глобальными переменными.Другой тип фальшивых классов возникает из-за того, что про- граммист полагает, что объектно ориентированное программиро- вание всегда «лучше», и применяет его в тех ситуациях, где оно не подходит. В этих случаях программист часто создает класс, который инкапсулирует специфический функционал, имеющий смысл толь- ко в контексте исходной программы, для которой он написан. Есть два способа проверить, пишете ли вы фальшивый класс или нет. За- дайте себе вопрос: «Могу я назвать класс кратко и понятно?» Если имя будет выглядеть как PayrollReportManagerAndPrintSpooler, по- видимому, у вас проблемы. Другой тест выглядит так: «если мне при- дется писать другую программу с похожим функционалом, можно ли этот класс использовать еще раз с небольшими изменениями? Или его придется кардинальным образом переписывать?»Даже в языке C++ появление фальшивых классов неизбежно, на- пример, когда нам надо инкапсулировать данные для использования в классах-коллекциях. Однако такие классы обычно маленькие и эле- ментарные. Когда мы избегаем создания фальшивых классов, наш код становится лучше.Однозадачники Если вам доводилось смотреть телевизионное шоу Good Eats, вы зна- ете, что ведущий Элтон Браун тратит массу времени, рассуждая, как оборудовать кухню с максимальной эффективностью. Часто он вос- стает против кухонных приспособлений, которые называет одноза-дачниками, подразумевая инструменты, хорошо решающие одну зада- чу, но не приспособленные более ни для чего. Разрабатывая классы, Решение задач с классами 171мы должны стремиться сделать их настолько общими, насколько это возможно, последовательно включая все функции необходимые для нашей программы.Один из способов сделать это состоит в использовании шаблон- ных классов . Это продвинутый способ с немного загадочным син- таксисом, однако он позволяет нам создавать классы, где у одного или более полей тип определяется в момент создания объекта клас- са. Шаблонные классы позволяют нам «выделить» основной функ- ционал. Например, наш класс studentCollection содержит много кода одинакового для любого класса, инкапсулирующего связный список. Вместо этого мы можем сделать шаблонный класс для об- щего связного списка, такого, чтобы тип данных внутри узлов спи- ска определялся в момент создания объекта шаблонного класса, а не программировался как studentRecord. Тогда полем нашего клас- са studentCollection будет объект шаблонного класса связного спи- ска, а не указатель на начало списка, и наш класс больше не сможет непосредственно управлять связным списком.Мы не будем рассматривать шаблонные классы в этой книге, од- нако, развивая ваши навыки проектировщика классов, вы должны всегда стремиться делать классы «многозадачниками». Когда вы об- наруживаете, что текущую задачу можно решить, используя класс, написанный тогда, когда вы даже не подозревали о ее существова- нии, вы испытываете чувство глубокого удовлетворения. УпражненияВы знаете, что я хочу вам сказать, не так ли? Вперед, попытаетесь сами!5.1.Давайте попробуем реализовать класс, используя базовый фреймворк. Рассмотрим класс, хранящий данные по автомоби- лям. У нас есть три элемента данных: название производителя, название модели (оба строковые) и год выпуска – целочислен- ное. Создайте класс с методами get/set для каждого поля клас- са. Убедитесь, что вы приняли верные решения о деталях, на- пример имени переменных. Необязательно пользоваться моей конвенцией наименования, важнее грамотно подходить к при- нятию решений и быть в них последовательными.5.2. Добавьте в наш автомобильный класс из предыдущего упражне- ния служебный метод, возвращающий полное описание авто- мобиля в формате строки, например, «1957 Chevrolet Impala». Добавьте второй служебный метод, возвращающий возраст ав- томобиля в годах.5.3. Возьмите функции для строк переменной длины из главы 4 (ap- pend, concatenate и characterAt) и используйте их для создания класса для строк переменной длины. Убедитесь, что вы реализо- вали все необходимые конструкторы, деструктор, а также пере- грузили оператор присваивания. 5.4. Для класса строк переменной длины из предыдущего упражне- ния замените метод characterAt перегруженным оператором []. Например, если myString является объектом нашего класса, тог- да выражение myString[1] должно возвращать то же значение, что и myString.characterAt(1).5.5. Для класса строк переменной длины из предыдущих упражне- ний добавьте метод remove, принимающий начальную позицию и количество символов и удаляющий это количество символов из середины строки. Например, myString.remove(5,3) удалит три символа, начиная с пятой позиции. Убедитесь, что ваш метод ра- ботает, когда значение любого из параметров некор ректно.5.6. Подумайте, можно ли ваш класс строк переменной длины улуч- шить. Например, нет ли общего функционала, который можно выделить в приватный служебный метод?5.7. Возьмите функции записей о студентах из главы 4 (addRecord и averageRecord) и используйте их для создания класса, представ- ляющего коллекцию записей о студентах, как ранее. Убедитесь, что реализовали все необходимые конструкторы, деструктор, а также перегрузили оператор присваивания.5.8. Классу коллекции записей о студентах из предыдущего упражне- ния добавьте метод RecordsWithinRange, принимающий нижнее и верхнее значение оценки как параметры и возвращающий но- вую коллекцию, состоящую из записей в этом диапазоне (исход- ная коллекция не меняется). Например, myCollection.Record- sWithinRange(75, 80)вернет коллекцию всех записей с оценками в диапазоне от 75 до 80 включительно. 173Эта глава посвящена рекурсии, при которой функция прямо или кос- венно вызывает саму себя. Рекур- сивное программирование выглядит так, будто оно должно быть простым. Действи- тельно, хорошее рекурсивное решение часто имеет простой, почти элегантный вид. Тем не менее очень часто путь к этому решению весьма непрост. Это связано с тем, что рекурсия требует от нас мыслить не так, как в случае с другими ти- пами программирования. Когда мы обрабатываем данные с помощью циклов, мы думаем о последовательной обработке, однако при обра- ботке данных с использованием рекурсии, наш обычный процесс по- следовательного мышления не помогает. У многих хороших, но еще не оперившихся программистов возникают проблемы с рекурсией, поскольку они не могут найти способ применения уже освоенных ими + " ! = 6 174 Глава 6навыков решения задач к задачам с рекурсией. В этой главе мы обсу- дим систематический подход к решению таких задач. Ответ заключа- ется в том, что мы будем называть Большой Рекурсивной Идеей, далее по тексту — БРИ. Эта идея настолько проста, что напоминает трюк, но она работает. Обзор основ рекурсии Синтаксис рекурсии не очень сложен. Трудность возникает, когда вы пытаетесь использовать рекурсию для решения задач. Рекурсия име- ет место всегда, когда функция сама себя вызывает, поэтому синтак- сис рекурсии представляет собой просто синтаксис вызова функции. Наиболее распространенной формой является прямая рекурсия, ког- да вызов функции происходит в теле этой же функции. Например:int factorial(int n) {X if (n == 1) return 1;else return n * Yfactorial(n — 1);}Эта функция, которая является общей, но неэффективной демон- страцией рекурсии, вычисляет факториал числа n. Например, если n равно 5, то факториал — это произведение всех чисел от 5 до 1, или 120. Обратите внимание на то, что в некоторых случаях рекурсии не проис- ходит. В этой функции, если параметр равен 1, мы просто возвращаем значение напрямую без какой-либо рекурсии X, это так называемый ба-зовый случай. В противном случае мы делаем рекурсивный вызов YДругой формой рекурсии является косвенная рекурсия — напри- мер, когда функция A вызывает функцию B, которая далее вызывает функцию A. Косвенная рекурсия редко используется в качестве ме- тода решения задач, поэтому мы не будем здесь ее обсуждать. Головная и хвостовая рекурсия Прежде чем обсуждать БРИ, нам нужно понять разницу между голов- ной и хвостовой рекурсией. В случае головной рекурсии рекурсивный вызов, когда он происходит, предваряет другие процессы обработки в функции (считайте, что он происходит вверху или в голове функции). В случае хвостовой рекурсии все наоборот — обработка происходит пе- ред рекурсивным вызовом. Выбор между двумя рекурсивными стиля- ми может показаться произвольным, однако в этом выборе заключа- ется все различие. Чтобы проиллюстрировать это различие, давайте рассмотрим две задачи. : Пассажиры Райской тропической железной дороги (РТЖД) с нетерпением ждут того мо- мента, когда смогут увидеть из окон поезда многочисленных красочных птиц. По этой причине руководство железной дороги очень заинтересовано в состоянии здоровья Решение задач с помощью рекурсии 175местной популяции попугаев и решает подсчитать количество попугаев, находящихся в пределах видимости с каждой железнодорожной платформы вдоль главной линии. На каждую платформу направлен сотрудник РТЖД (см. рис. 6.1), который, безусловно, спо- собен подсчитать количество попугаев. К сожалению, работа усложняется из-за прими- тивной телефонной системы. С каждой платформы можно позвонить только на соседние платформы. Как передать общее число попугаев на терминал главной линии? Рис. 6.1. Сотрудники пяти станций могут общаться только со своими непосредственными соседями Предположим, что Арт насчитал на главном терминале 7 попугаев, Белинда — 5 попугаев, Кори — 3 попугая, Дебби — 10 попугаев, и 2 попу- гая насчитал Эван на последней станции. Таким образом, общее число попугаев составляет 27. Вопрос в том, как сотрудники собираются ра- ботать вместе, чтобы сообщить об этом Арту? Любое решение этой за- дачи потребует последовательной передачи сообщения от основного терминала до конца линии и обратно. Сотрудник на каждой платформе должен будет подсчитать количество попугаев, а затем сообщить о сво- их наблюдениях. Тем не менее существуют два разных подхода к реа- лизации этой цепочки сообщений, которые соответствуют головной и хвостовой рекурсии в программировании. 1   ...   17   18   19   20   21   22   23   24   ...   34

Абстрактные типы данных Абстрактный тип данных, как говорилось в главе 5, представляет со- бой тип, определяемый его операциями, а не тем, как эти операции выполняются. Хорошим примером является тип стек, который мы уже несколько раз использовали в этой книге. Абстрактные типы данных похожи на шаблоны в плане определения эффектов опера- ций, но они конкретно не определяют, как эти операции реализу- ются. Тем не менее, как и в случае с алгоритмами, для этих опера- ций существуют хорошо известные методы реализации. Например, стек может быть реализован с использованием любого количества таких основополагающих структур данных, как связный список или Решение задач с помощью повторного использования кода 209массив. Однако когда мы выбираем конкретную структуру данных, решения, связанные с ее реализацией, иногда оказываются уже при- нятыми. Предположим, мы реализовали стек с помощью связного списка и не можем обернуть существующий связный список, но нам требуется написать собственный код списка. Поскольку стек являет- ся структурой типа «последним пришел — первым ушел» (last-in-first- out), нам имеет смысл добавлять и удалять элементы только на од- ном конце связанного списка. Кроме того, имеет смысл добавлять и удалять элементы только в начале списка. Теоретически вы можете добавлять и удалять элементы в конце, однако это приведет к неэф- фективному обходу всего списка при каждой вставке или удалении. Чтобы избежать этих обходов, потребуется двусвязный список с от- дельным указателем на последний узел в списке. Вставка и удаление элементов в начале списка делает возможной простейшую, наибо- лее эффективную реализацию, поэтому практически все реализации стеков на основе связных списков одинаковы. Таким образом, хотя слово абстрактный в названии абстракт-ный тип данных означает, что тип является концептуальным и не со- держит деталей, относящихся к реализации, на практике, если вы решите реализовать абстрактный тип данных в своем коде, вам не придется разрабатывать реализацию с нуля. Вместо этого в качестве руководства вам послужат существующие реализации данного типа. Библиотеки В программировании библиотека представляет собой набор свя- занных фрагментов кода. Как правило, библиотека включает код в скомпилированной форме вместе с необходимыми объявлениями исходного кода. Библиотеки могут включать автономные функции, классы, объявления типов или что-либо еще, что может использо- ваться в коде. В языке C++ наиболее очевидными примерами явля- ются стандартные библиотеки. Функция strcmp, которую мы исполь- зовали в предыдущих главах, была взята из старой библиотеки языка C cstring, такие контейнерные классы, как vector, — из стандартной библиотеки шаблонов C ++ и даже макрос NULL, который мы исполь- зовали во всем коде на основе указателей, не является частью языка C++, а определяется в заголовочном файле библиотеки, stdlib.h. По- скольку так много базовых функций содержится в библиотеках, их использование в современном программировании неизбежно. Вообще, использование библиотеки является примером хорошего повторного использования кода. Код включен в библиотеку, посколь- ку он обеспечивает функциональность, которая обычно необходима в различных программах, — библиотечный код помогает программи- стам избежать необходимости «изобретать колесо». Тем не менее как разработчики программ при использовании библиотечного кода мы должны стремиться научиться на своем опыте, а не просто использо- вать обходной путь. Далее в этой главе мы рассмотрим пример. 210 Глава 7Обратите внимание на то, что, хотя многие библиотеки явля- ются библиотеками общего назначения, другие разработаны как ин-терфейсы прикладного программирования (API), предоставляющие про- граммисту, работающему с высокоуровневым языком, упрощенное или более последовательное представление об основополагающей платформе. Например, язык Java включает в себя API под названи- ем JDBC, который предоставляет классы, позволяющие программам взаимодействовать с реляционными базами данных стандартным способом. Другой пример — это DirectX, который предоставляет программистам игр Microsoft Windows обширную функциональ- ность для работы со звуком и графикой. В обоих случаях библиоте- ка обеспечивает связь между высокоуровневой программой и фунда- ментальным аппаратным и программным обеспечением — с движком базы данных в случае JDBC и графическим и звуковым оборудовани- ем в случае DirectX. Более того, в обоих случаях повторное исполь- зование кода не только допустимо, но и желательно для всех прак- тических целей. Программист базы данных, работающий с языком Java, или графический программист, пишущий код C++ для Windows, будет использовать API, если не перечисленные выше API, то что-то еще, но программист не будет с нуля разрабатывать новое соедине- ние с платформой. Изучение компонентов Компоненты настолько полезны, что программисты используют их при любой возможности. Тем не менее, чтобы использовать компо- нент для решения задачи, программист должен знать о его существо- вании. В зависимости от того, насколько точно вы их определяете, доступные компоненты могут исчисляться сотнями или даже тыся- чами, а начинающий программист будет знать только о некоторых из них. Поэтому хороший программист всегда должен стараться обо- гащать свои знания о компонентах. Такое накопление знаний про- исходит двумя разными способами: программист может специально выделить время для изучения новых компонентов или поискать ком- понент для решения конкретной задачи. Мы будем называть первый подход исследовательским обучением, а второй — обучением по мере необ-ходимости. Чтобы развиваться как программисту, вам нужно будет использовать оба подхода. После освоения синтаксиса выбранно- го вами языка программирования, изучение новых компонентов — один из основных способов самосовершенствования в качестве про- граммиста.Исследовательское обучение Давайте начнем с примера исследовательского обучения. Предполо- жим, нам нужно узнать больше о шаблонах проектирования. К сча- стью, существует общее соглашение относительно того, какие шаб- лоны проектирования являются наиболее полезными или часто Решение задач с помощью повторного использования кода 211используемыми, поэтому мы могли бы начать с любого количества ресурсов по этой теме и быть достаточно уверенными в том, что не упустим ничего важного. Мы бы выиграли от простого нахождения списка шаблонов проектирования и его изучения, однако мы бы до- стигли большего понимания, если бы реализовали некоторые из этих шаблонов. Один шаблон, который мы можем найти в типичном списке, назы- вается стратегией или политикой. Это идея, позволяющая выбрать алго- ритм или часть алгоритма во время выполнения программы. В самой чистой форме, в форме стратегии, этот шаблон позволяет изменить способ функционирования метода или функции, не изменяя результат. Например, метод класса, который сортирует данные или предполагает их сортировку, может допускать выбор метода сортировки (например, быстрая сортировка или сортировка вставками). Результат — отсорти- рованные данные — во всех случаях будет одним и тем же, однако пре- доставление клиенту возможности выбора метода сортировки может обеспечить некоторые преимущества в плане производительности. На- пример, клиент может избежать использования быстрой сортировки для данных с высокой степенью дублирования. В форме политики вы- бор клиента влияет на результат. Например, предположим, что класс представляет собой набор игральных карт. Политика сортировки мо- жет определить, считаются ли тузы самыми старшими картами (стар- ше короля) или самыми младшими (младше 2). Применение полученных знаний на практикеИзучив предыдущий абзац, вы узнали, что представляет собой ша- блон стратегия/политика, но вы не сделали его своим инструмен- том. Это подобно разнице между просмотром инструментов в ма- газине и их фактической покупкой и использованием. Поэтому давайте возьмем этот шаблон проектирования с полки и попробу- ем его в деле. Самый быстрый способ опробовать новую технику — включить ее в уже написанный вами код. Давайте сформулируем за- дачу, которая может быть решена с использованием этого шаблона и построена на уже написанном нами коде. : В каждом классе школы назначается староста («первый ученик»), который отвечает за поддержание порядка в классе в отсутствие учителя. Первоначально это звание при- сваивалось ученику с наивысшим уровнем успеваемости, однако теперь некоторые преподаватели считают, что староста должен определяться по старшинству, то есть по наименьшему идентификационному номеру ученика, поскольку они назначаются последовательно. Другая часть преподавателей считает традицию избрания старосты смехотворной и намеревается протестовать против нее, просто выбрав ученика, имя которого идет первым по алфавиту в ведомости успеваемости класса. Наша задача — изменить класс коллекции учеников, добавив метод для извлечения из этой коллекции старосты, при этом учитывая критерии отбора различных групп учителей. 212 Глава 7Как видите, решение этой задачи подразумевает использование шаблона в форме политики. Мы хотим, чтобы наш метод, возвраща- ющий имя старосты, возвращал имена разных учеников в зависи- мости от выбранного критерия. Чтобы реализовать это средствами языка C++, мы будем использовать указатели на функции. В главе 3 мы кратко рассмотрели эту концепцию в действии на примере функ- ции qsort, принимающей указатель на функцию, которая сравни- вает два элемента в массиве, подлежащем сортировке. Мы сделаем что-то подобное и здесь; мы используем набор функций сравнения, которые возьмут два наших объекта studentRecord и определят, явля- ется ли первый ученик «лучше» второго, исходя из их оценок, иден- тификационных номеров или имен. Для начала мы должны определить тип для наших функций срав- нения: typedef bool X(* rstStudentPolicy)(studentRecord r1, studentRecord r2);Это объявление создает тип с именем rstStudentPolicy в каче- стве указателя на функцию, которая возвращает bool и принимает два параметра типа studentRecord. Круглые скобки вокруг * rstStudent-PolicyX необходимы, чтобы исключить интерпретацию объявления как функции, которая возвращает указатель на bool. После добавле- ния этого объявления мы можем создать три функции политики: bool higherGrade(studentRecord r1, studentRecord r2) {return r1.grade() > r2.grade();}bool lowerStudentNumber(studentRecord r1, studentRecord r2) {return r1.studentID() < r2.studentID();}bool nameComesFirst(studentRecord r1, studentRecord r2) {return Xstrcmp(r1.name().c_str()Y, r2.name().c_str()Y )Z< 0;}Первые две функции очень просты: higherGrade возвращает зна- чение true, когда первая запись содержит более высокую оценку, а lowerStudentNumber возвращает значение true, когда первая запись со- держит меньший идентификационный номер ученика. Третья функ- ция nameComesFirst по сути представляет собой то же самое, но требу- ет использования библиотечной функции strcmp X, которая ожидает две строки в «стиле С», то есть нуль-терминированные массивы сим- волов вместо объектов string. Поэтому мы должны вызывать метод c_str()Y в строках name в обеих записях с данными об учениках. Функ- ция strcmp возвращает отрицательное число, когда первая строка следует по алфавиту перед второй, поэтому мы проверяем возвращен- ное значение, чтобы посмотреть, не превышает ли оно значение 0 ZТеперь мы готовы изменить сам класс studentCollection: class studentCollection {private:struct studentNode {studentRecord studentData; Решение задач с помощью повторного использования кода 213studentNode * next;};public:studentCollection();studentCollection();studentCollection(const studentCollection &copy);studentCollection& operator=(const studentCollection &rhs);void addRecord(studentRecord newStudent);studentRecord recordWithNumber(int IDnum);void removeRecord(int IDnum);X void setFirstStudentPolicy( rstStudentPolicy f);Y studentRecord rstStudent();private:Z rstStudentPolicy _currentPolicy;typedef studentNode * studentList;studentList _listHead;void deleteList(studentList &listPtr);studentList copiedList(const studentList copy);};Это объявление класса, которое мы видели в главе 5 с тремя но- выми членами: приватным членом данных, _currentPolicy Z, для хранения указателя на одну из наших функций-политик; методом setFirstStudentPolicyZ для изменения этой политики; и самим ме- тодом rstStudent Y, который возвращает имя старосты в соответ- ствии с текущей политикой. Код для метода setFirstStudentPolicy прост: void studentCollection::setFirstStudentPolicy( rstStudentPolicy f) {_currentPolicy = f;}Нам также нужно изменить конструктор по умолчанию для ини- циализации текущей политики: studentCollection::studentCollection() {_listHead = NULL;_currentPolicy = NULL;}Теперь мы готовы создать метод rstStudent: studentRecord studentCollection:: rstStudent() {X if (_listHead == NULL || _currentPolicy == NULL) {studentRecord dummyRecord(-1, -1, "");return dummyRecord;}studentNode * loopPtr = _listHead;Y studentRecord rst = loopPtr->studentData;Z loopPtr = loopPtr->next;while (loopPtr != NULL) {if ([_currentPolicy(loopPtr->studentData, rst)) { rst = loopPtr->studentData;}\loopPtr = loopPtr->next;}return rst;} 214 Глава 7Этот метод начинается с проверки специальных случаев. При отсутствии списка для проверки или политики X мы возвращаем фиктивную запись. В противном случае мы обходим список, чтобы обнаружить ученика, лучше всего соответствующего текущей поли- тике, используя базовые методы поиска, которые многократно при- меняли в этой книге. Мы присваиваем запись в начале списка пере- менной rst Y, запускаем нашу переменную цикла на второй записи в списке Z и начинаем обход. Внутри цикла обхода вызов текущей функции политики [ сообщает нам, является ли рассматриваемый нами ученик «лучшим учеником» по сравнению с лучшим учеником, определенным нами до сих пор, исходя из текущего критерия. По- сле завершения цикла мы возвращаем имя старосты, то есть «перво- го ученика» \Анализ решения задачи выбора старосты Решив задачу с помощью шаблона стратегии/политики, мы скорее распознаем ситуации, в которых применим этот метод, чем если бы мы просто о нем прочитали, но так и не опробовали. Мы также можем проанализировать нашу задачу, чтобы начать формировать собственное мнение о ценности метода, о том, когда его использо- вание может быть уместным, а когда ошибочным или по крайней мере принести больше неприятностей, чем пользы. Одна мысль, которая могла у вас возникнуть по поводу этого конкретного шаб- лона, заключается в том, что он ухудшает инкапсуляцию и сокры- тие информации. Например, если клиентский код предоставляет функции политики, он требует доступа к типам, которые обычно остаются внутренними для класса, в данном случае к типу studen- tRecord. (Мы рассмотрим способ решения этой проблемы в упраж- нениях). Это означает, что в клиентском коде может произойти сбой, если мы когда-либо изменим этот тип, и мы должны сопоста- вить эту проблему с преимуществами шаблона, прежде чем приме- нять его в других проектах. В предыдущих главах мы уже говорили, что знание того, когда следует использовать тот или иной метод, а когда не следует, так же важно, как знание того, как его использо- вать. Изучение собственного кода позволяет вам ответить на этот крайне важный вопрос. Для дальнейшей практики вы можете просмотреть свою библи- отеку готовых проектов, чтобы найти код, который можно перера- ботать с использованием этого метода. Помните о том, что большая часть «настоящего» программирования предполагает дополнение или изменение существующей базы кода, поэтому данная практика отлично подходит для подобных модификаций, а также развивает ваши навыки работы с конкретным компонентом. Более того, одним из преимуществ хорошего повторного использования кода является то, что мы учимся на этом, а данная практика позволяет получить от обучения максимальную пользу. Решение задач с помощью повторного использования кода 215Обучение по мере необходимости Предыдущий раздел был посвящен тому, что можно было бы назвать «блуждающим обучением». Хотя такие странствия ценны для про- граммистов, иногда нам приходится двигаться к определенной цели. Если вы работаете над конкретной задачей, особенно если вам нуж- но успеть к какому-то сроку и вы считаете, что компонент может вам очень помочь, вам не нужно бесцельно блуждать по миру программи- рования в надежде наткнуться на то, что вам нужно. Вместо этого вы хотите как можно быстрее найти компонент или компоненты, непо- средственно применимые к вашей ситуации. Однако проблема вот в чем: как вы найдете то, что вам нужно, если вы точно не знаете, что ищете? Рассмотрим следующую задачу. : D ' ' # $ 9 В проекте программы будет использоваться ваш класс studentCollection. Клиент- ский код нуждается в возможности обхода всех учеников в коллекции. Очевидно, что для обеспечения сокрытия информации клиентскому коду не может быть предоставлен прямой доступ к списку, однако эффективность обходов — непременное условие. Поскольку ключевым словом в этом описании является эффек-тивность, давайте уточним, что это значит в данном случае. Предпо- ложим, что отдельный объект нашего класса studentCollection со- держит 100 учеников. Если бы у нас был прямой доступ к связному списку, мы могли бы написать цикл для обхода этого списка, кото- рый бы обрабатывал список 100 раз. Это максимально эффективный обход списка. Любое решение, требующее, чтобы мы обрабатывали список более 100 раз для определения результата, будет считаться неэффективным. Без требования эффективности мы можем попытаться решить эту задачу, добавив в наш класс простой метод recordAt, который бу- дет возвращать запись с данными об ученике в конкретной позиции в коллекции, присвоив первой записи номер 1: studentRecord studentCollection::recordAt(int position) {studentNode * loopPtr = _listHead;int i = 1;X while (loopPtr != NULL && i < position) {i++;loopPtr = loopPtr->next;}if (loopPtr == NULL) {Y studentRecord dummyRecord(-1, -1, "");return dummyRecord;} else {Z return loopPtr->studentData;}}В этом методе используем цикл X, чтобы обходить список до тех пор, пока мы не достигнем желаемой позиции или конца списка. 1   ...   22   23   24   25   26   27   28   29   ...   34


Решение задач с указателями и динамической памятью 107
double * doublePointer = new double;
Доступ к содержимому памяти с помощью указателя называется операцией разыменования и осуществляется с помощью оператора
*
, который указывается слева от идентификатора указателя. То есть также как и при объявлении. А содержание операции определяется по контексту. Например:
X *doublePointer = 35.4;
Y double localDouble = *doublePointer;
Мы записали числовое значение типа double в участок памяти, который был выделен в предыдущем примере
X
, а потом присвоили содержимое этой памяти переменной localDouble
Y
Чтобы освободить память, выделенную при помощи оператора new
, когда в ней больше нет нужды, мы используем ключевое слово delete
:
delete doublePointer;
Этот процесс детально описан в разделе «Вопросы памяти» да- лее в этой главе.
Преимущества использования указателей
Использование указателей существенно расширяет возможности по сравнению с использованием статической памяти, а также позволя- ет использовать память более эффективно. Перечислим три основ- ных преимущества, возникающие при использовании указателей:
y
использование структур данных, размер которых определяет- ся во время выполнения программы;
y
использование динамических структур данных, которые мо- гут изменять свой размер во время выполнения программы;
yразделение памяти.
А теперь давайте рассмотрим каждое из них подробнее.
Структуры данных, размер которых определяется
во время выполнения программы
Применение указателей позволяет создавать массивы, размер которых определяется во время выполнения программы, вместо того, чтобы определять их размер при проектировании приложения. Это убере- гает нас от выбора между возможным переполнением массива и нера- циональным использованием памяти в случае создания максимально больших массивов. Мы уже рассматривали структуры данных, размер которых определяется во время выполнения программы в разделе
«В каких случаях использовать массивы». И вернемся к этому вопросу позже, в разделе «Строки переменной длины» далее в этой главе.

108 Глава 4
Динамические структуры
Также с помощью указателей можно создавать структуры данных, ко- торые при необходимости способны увеличиваться или уменьшать- ся во время выполнения программы. Связный список, который вы, скорее всего, уже встречали, — самый простой пример динамической структуры данных. Несмотря на исключительно последовательный доступ к данным, связный список всегда занимает ровно столько памя- ти, сколько требуется для хранения его данных и ни байтом больше.
Позже вы увидите, что более сложные структуры данных, основанные на указателях, используют упорядочивание и «формы», обеспечиваю- щие лучшее отражение связей данных, чем это реализовано в масси- вах. По этой причине, даже учитывая произвольный доступ к данным массива, который структуры, основанные на указателях, обеспечить не могут, операция поиска (когда мы ищем элемент, наилучшим обра- зом удовлетворяющий заданным критериям) может осуществляться намного быстрее в структурах, основанных на указателях. Позже в этой главе мы воспользуемся подобным преимуществом при создании структуры данных для хранения студенческих карточек, которая мо- жет увеличиваться по мере необходимости.
Разделение памяти
Указатели позволяют осуществлять совместный доступ к памяти, что повышает эффективность программного кода. Например, при вы- зове функции мы можем передать в нее указатель вместо того, что- бы копировать данные. Такой способ называется передачей по ссылке.
Скорее всего, вы уже сталкивались с этим раньше. Это те самые па- раметры, у которых символ & указан между типом и именем в списке параметров функции:
void refParamFunction (int
X& x) {
Yx = 10;
}
int number = 5;
refParamFunction(
Z number);
cout <<
[ number << "\n";
ПРИМЕЧАНИЕ.
Пробелы до и после символа & не обязательны, я поставил
их по эстетическим соображениям. В коде других разработчиков вы можете
встретить следующие формы записи: int& x, int &x и int&x.
В примере параметр x
X
является не копией аргумента number
Z
, а представляет собой ссылку на участок памяти, в котором хранится значение переменной number. Таким образом, при изменении пере- менной x
Y
изменяется значение в ячейки памяти переменной number и в итоге на экран будет выведено 10
[
. Передача по ссылке может также применяться и для возвращения результата из функции, как было показано в этом примере. В широком смысле передача по ссыл- ке позволяет вызванной и вызывающей функциям совместно исполь-

Решение задач с указателями и динамической памятью
1   ...   9   10   11   12   13   14   15   16   ...   34
109
зовать память, тем самым снижая накладные расходы. Если перемен- ная, передаваемая в качестве аргумента, занимает килобайт памяти, то при передаче по ссылке вместо килобайта копируется только 32- или 64-битный указатель. При помощи ключевого слова const мы мо- жем запретить функции изменять параметр, переданный по ссылке:
int anotherFunction(const int & x);
Ключевое слово const в объявлении ссылочного параметра x оз- начает, что функция anotherFunction получит ссылку на аргумент, переданный при вызове, но не сможет изменять значение этого ар- гумента, так как он является константой.
В общем, мы можем использовать указатели подобным образом для того, чтобы различные части программы или структуры данных, задействованные в программе, могли использовать одни и те же дан- ные без дополнительных затрат памяти.
В каких случаях использовать указатели
Как и массивы, указатели имеют свои недостатки и должны приме- няться только тогда, когда это действительно необходимо. Как по- нять, что применение указателя необходимо? Так как у нас есть толь- ко список возможностей, предоставляемых указателями, мы можем сказать, что их использование оправданно при возникновении по- требности в одной или нескольких из этих возможностей. Если ва- шей программе требуется структура данных, но вы не можете зара- нее определить объем этих данных. Если вам требуется структура, которая может увеличиваться или уменьшаться во время выполнения программы. Или вы собираетесь передавать объемные данные между частями программы, то можете применять указатели. Если же таких потребностей нет, то вам следует держаться подальше от указателей и динамического распределения памяти.
Так как указатели имеют печальную репутацию одной из са- мых сложных особенностей языка С++, вы можете предположить, что программисты стараются не применять их без лишней необхо- димости. Я не единожды удивлялся, обнаружив обратное. Иногда программисты обманывают сами себя, предполагая, что указатели необходимы. Предположим, вы вызываете чужую функцию из биб- лиотеки или интерфейса прикладного программирования со следу- ющим прототипом:

void compute(int input, int* output);
Мы можем предположить, что эта функция написана на язы- ке С, а не С++, и именно поэтому она использует указатель вместо ссылки (&) для создания «исходящего» параметра. При вызове дан- ной функции программист может небрежно сделать что-то вроде этого:

110 Глава 4
int num1 = 10;
int* num2 = new int;
compute(num1, num2);
Этот код неэффективно использует память , так как он создает лиш- ний указатель. Вместо памяти для двух переменных типа int, он захваты- вает место для двух переменных типа int и для указателя. Этот код так- же неэффективно использует время, так как выделение лишней памяти требует дополнительного времени (это мы рассмотрим в следующем разделе). И наконец, программист не должен забывать освобождать вы- деляемую память с помощью ключевого слова delete. Всего этого мож- но избежать, если использовать другой аспект оператора & , который по- зволяет получить адрес статической переменной, например:
int num1 = 10;
int num2;
compute(num1, &num2);
Строго говоря, мы все еще используем указатель во второй вер- сии, но делаем это косвенно, без объявления или динамического вы- деления памяти.
Вопросы памяти
Чтобы разобраться, каким образом работает динамическое распреде- ление памяти, нужно понимать механизм работы памяти в целом. Это одна из тех тем, ради которых начинающим программистам стоит из- учать язык С++. В конце концов, все программисты должны понимать механизм работы системы памяти в современных компьютерах, и язык
С++ ставит вас лицом к лицу с этой темой. Другие языки программиро- вания скрывают большинство неприглядных подробностей работы си- стемы памяти, поэтому начинающие программисты полагают, будто эти подробности их не касаются, что в корне неверно. Эти подробности ни- кого не касаются, только пока все работает. Как только возникает про- блема, дальнейшее пренебрежение основами работы памяти создает не- преодолимое препятствие между программистом и ее решением.
Стек и куча
Язык С++ выделяет оперативную память в двух местах: стеке и куче.
Как следует из названий, стек (от англ. stack – стопка) – аккуратный и организованный, а куча – бессвязная и беспорядочная. Название стоп-
ка очень меткое, так как помогает визуализировать устройство стека.
Представьте стопку коробок наподобие той, что показана на рис. 4.1
(а). Когда вам нужно отправить коробку на хранение, вы просто стави- те ее наверх стопки. Чтобы достать определенную коробку из стопки, вы сначала должны снять все коробки, стоящие сверху. Говоря языком программирования, однажды выделив блок памяти в стеке (коробку), вы уже не можете изменить его размер, так как следом расположены другие блоки памяти (коробки, стоящие сверху).

Решение задач с указателями и динамической памятью 111
Язык С++ позволяет создавать ваш собственный стек, работаю- щий по определенному алгоритму, но несмотря на это ваша програм- ма все равно всегда будет использовать так называемый стек вызовов .
Каждый раз при вызове функции (включая функцию main) будет вы- деляться блок памяти в голове стека. Такой блок называется запись ак-
тивации . Разговор обо всем его содержимом выходит за рамки нашей книги, но для решения задач нам будет достаточно знать, что запись активации является местом хранения переменных. Память для всех локальных переменных, включая параметры функции, выделяется внутри записи активации. Давайте рассмотрим пример:
int functionB(int inputValue) {
X return inputValue – 10;
}
int functionA(int num) {
int localVariable = functionB(num * 10);
return localVariable;
}
int main()
{
int x = 12;
int y = functionA(x);
return 0;
}
В этом коде функция main вызывает функцию functionA
, кото- рая, в свою очередь, вызывает функцию functionB
На рис. 4.1 (б) можно увидеть упрощенную версию организации стека вызовов перед возвращением управления из functionB
X
. За- писи активации всех трех функций будут расположены в стеке друг за другом, начиная с функции main в глубине стека. (Чтобы запутать вас еще больше, уточню, что стек может располагаться в памяти в об- ратном направлении, от больших адресов ячеек к меньшим. Однако ничего плохого не произойдет, если вы забудете об этом.) Логически запись активации main располагается в глубине стека, над ней лежит запись активации functionA, а еще выше запись активации functionB.
Ни одна из нижних записей активации не может вернуть управление, пока не вернет управление functionB.
Рис. 4.1. Стопка коробок и стек вызовов функции

112 Глава 4
Если стек представляет собой хорошо организованную структуру, то куча , напротив, не имеет практически никакой организации. Пред- ставим, что вы опять храните коробки, но это хрупкие коробки и вы не можете поставить их друг на друга. У вас есть большая пустая комната для хранения коробок, и вы можете ставить их на пол в любое место.
А так как коробки тяжелые, то вы стараетесь поставить их на ближай- шее свободное к двери место. Эта структура имеет свои преимущества и недостатки по сравнению со стеком. С одной стороны, такая система хранения более гибкая и позволяет вам добраться до любой коробки в любой момент. С другой стороны, в комнате очень быстро начинается неразбериха. А если все коробки разного размера, то никак не получа- ется использовать все полезное пространство пола. В итоге у вас пропа- дает слишком много места между коробками, так как туда уже ничего не помещается. Так как коробки сложно передвигать, то после выноса не- скольких остаются промежутки, которые трудно заполнить. Если гово- рить языком программирования, то наша куча представляет собой как раз такой пол. Участок памяти идущих подряд адресов ячеек. Если про- грамма предусматривает частые выделения и высвобождения памяти, то в итоге в памяти остается множество пустот между заполненными участками. Эта проблема носит название фрагментация памяти .
Для каждой программы создается своя собственная куча, память в которой распределяется динамически. Обычно в языке С++ это происходит с помощью оператора new, но также можно воспользо- ваться и старой функцией языка С для выделения памяти — malloc.
Каждый вызов оператора new (функции malloc ) выделяет кусок памя- ти в куче и возвращает указатель на него. Каждый вызов оператора delete
(или функции free , если память выделили с помощью malloc) возвращает выделенный кусок в свободный резерв кучи. Из-за фраг- ментации можно использовать далеко не всю память из резерва.
Если в начале программы в куче выделяется память под переменные
А, В, и С, то можно ожидать, что они будут соседствовать. Если мы удаляем переменную В, то оставшийся от нее участок памяти мож- но заполнить только совпадающей или меньшей по размеру заявкой, пока переменные А или С не будут удалены.
Рис. 4.2 наглядно демонстрирует положение дел. В части (а) пока- зан усеянный коробками пол комнаты. В какой-то момент простран- ство в комнате, возможно, было неплохо организовано, но теперь оно используется беспорядочно. Теперь некуда поставить малень- кую коробку (б), при том что суммарное свободное пространство значительно превосходит ее по размерам. В части (в) представлена небольшая куча. Она поделена пунктирными линиями на минималь- ные (неделимые) ячейки памяти, которые могут быть однобайтовы- ми, размером с машинное слово или более крупными – это зависит от менеджера кучи. Участки, закрашенные серым, представляют со- бой выделенную память. Для наглядности проставлена нумерация в одном выделенном блоке. Как и в случае с фрагментированным по- лом, свободная память фрагментированной кучи разбита на отдель-

Смотрите также файлы