ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 429
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
216 Глава 7
По завершении цикла, если был достигнут конец списка, мы создаем и возвращаем фиктивную запись
Y
или возвращаем запись в указан- ной позиции
Z
. Проблема в том, что мы производим обход для на- хождения только одной записи ученика. Этот обход необязательно полон, поскольку мы остановимся, когда достигнем желаемой пози- ции, но тем не менее это обход. Предположим, что клиентский код пытается усреднить оценки учащихся: int gradeTotal = 0;
for (int recNum = 1; recNum <= numRecords; recNum++) {
studentRecord temp = sc.recordAt(recNum);
gradeTotal += temp.grade();
}
double average = (double) gradeTotal / numRecords;
Для этого сегмента кода предположим, что sc — это ранее объяв- ленная и заполненная коллекция studentCollection, а recNum пред- ставляет собой переменную типа int, в которой хранится количе- ство записей. Предположим, что значение recNum равно 100. При поверхностном взгляде на этот код вам может показаться, что вы- числение среднего значения требует всего 100 запусков цикла, одна- ко, поскольку каждый вызов recordAt сам по себе является частич- ным обходом списка, этот код предполагает 100 обходов, каждый из которых будет включать около 50 запусков цикла для среднего слу- чая. Таким образом, вместо 100 шагов, что считалось бы эффектив- ным, для этого может потребоваться около 5000 шагов, что было бы очень неэффективно.
Когда следует искать компонент
Теперь мы столкнулись с реальной проблемой. Предоставить клиен- ту доступ к членам коллекции для совершения обхода легко; обеспе- чить эффективность такого доступа сложно. Разумеется, мы могли бы решить эту задачу, используя только собственные возможности, одна- ко мы могли бы достичь решения намного быстрее с помощью ком- понента. Первым шагом при поиске неизвестного компонента, ко- торый может помочь нам решить задачу, является предположение о том, что такой компонент на самом деле существует. Иными словами, вы не найдете компонент, если не начнете его искать. Поэтому, чтобы извлечь из компонентов максимальную пользу, вам нужно уметь опре- делять ситуации, где они могут пригодиться. Если вы застрянете на каком-то аспекте проблемы, попробуйте сделать следующее.
1. Сформулируйте проблему в общем виде.
2. Спросите себя: может ли это быть распространенной пробле- мой?
Первый шаг важен, потому что если мы сформулируем задачу так: «Позволить клиентскому коду эффективно вычислять среднюю оценку учеников в связном списке записей, инкапсулированных в классе», то это покажется характерным для нашей ситуации. Одна-
Решение задач с помощью повторного использования кода 217
ко если мы сформулируем задачу так: «Позволить клиентскому коду эффективно обходить связный список без предоставления прямого доступа к указателям списка», то мы начнем понимать, что это мо- жет быть распространенной проблемой. Поскольку программы ча- сто хранят связные списки и другие структуры с последовательным доступом в классах, мы можем предположить, что другие програм- мисты должны были выяснить, как можно обеспечить эффективный доступ к каждому элементу структуры.
Нахождение компонента
Теперь, когда мы готовы искать, пришло время найти наш компо- нент. Чтобы все было ясно, давайте переформулируем исходную за- дачу программирования как исследовательскую проблему: «Найдите компонент, который можно использовать для изменения класса stu- dentCollection таким образом, чтобы клиентский код мог эффектив- но обходить внутренний список». Как мы можем решить эту задачу?
Мы могли бы начать с рассмотрения любого из наших типов ком- понентов: шаблонов, алгоритмов, абстрактных типов данных или библио тек.
Предположим, что мы начали с рассмотрения стандартных биб- лиотек C++. Мы не обязательно будем искать класс для «включения» в решение, вместо этого мы могли бы поискать идеи в библиотеке клас- сов, напоминающей класс studentCollection. Это подразумевает при- менение стратегии поиска аналогии, которую мы использовали для решения задач по программированию. Если мы найдем класс с анало- гичной проблемой, то сможем воспользоваться его аналогичным ре- шением. В ходе нашего предыдущего рассмотрения библиотеки C++ мы познакомились с такими его контейнерными классами, как vec- tor
, и нам следует искать контейнерный класс, который больше всего похож на класс studentCollection. Если мы обратимся к нашему лю- бимому ресурсу, посвященному C++, будь то книга или интернет-сайт, и рассмотрим контейнерные классы C++, мы увидим там «контейнер последовательности» под названием list, который соответствует на- шему запросу. Позволяет ли класс list клиентскому коду совершать эффективный обход? Да, используя объект, известный как итератор.
Мы видим, что класс list предусматривает методы begin и end, созда- ющие итераторы, которые являются объектами, которые могут ссы- латься на определенный элемент в списке и инкрементироваться, чтобы итератор мог сослаться на следующий объект в списке. Если intList представляет собой list, заполненный целыми числа- ми, а iter — это list::iterator, то мы могли бы отобразить все целые числа в списке с помощью следующего кода: iter = intList.begin();
while (iter != intList.end()) {
cout << *iter << "\n";
iter++;
}
218 Глава 7
Благодаря использованию итератора класс list решил пробле- му, предоставив клиентскому коду механизм для эффективного об- хода списка. Сейчас мы можем подумать о том, чтобы поместить сам класс list в класс studentCollection, заменив наш самодельный связный список. Затем мы могли бы создать методы begin и end для нашего класса, которые обернули бы те же методы из встроенного объекта списка, и проблема была бы решена. Однако это напрямую связано с проблемой хорошего или плохого повторного использо- вания кода. Когда мы полностью поймем концепцию итератора и сможем самостоятельно воспроизвести ее в собственном коде, включение в код существующего класса из стандартной библиотеки шаблонов будет хорошим, а вероятно, и лучшим вариантом. Если мы не сможем этого сделать, то использование класса list станет обход- ным путем, который не поможет нам вырасти в области программи- рования. Иногда, конечно, нужно использовать компоненты, кото- рые мы не можем воспроизвести сами, однако если мы привыкнем к зависимости от других программистов при решении задач, то риску- ем никогда не научиться решать задачи самостоятельно.
Итак, давайте самостоятельно реализуем итератор. Прежде чем мы это сделаем, давайте кратко рассмотрим другие способы, с помощью которых мы могли бы прийти к тому же самому результату. Мы нача- ли поиск со стандартных библиотек шаблонов, однако могли бы начать искать в другом месте. Например, мы могли бы просмотреть список распространенных шаблонов проектирования. Под заголовком «пове- денческие шаблоны» мы бы нашли шаблон iterator, в котором клиенту предоставляется последовательный доступ к коллекции элементов без раскрытия базовой структуры этой коллекции. Это именно то, что нуж- но, однако мы могли бы обнаружить это решение только, осуществив поиск в списке шаблонов или вспомнив о том, что оно нам уже попа- далось в ходе предыдущего исследования шаблонов. Мы могли бы на- чать поиск с абстрактных типов данных, потому что список вообще и
связный список в частности — распространенные абстрактные типы дан- ных. Тем не менее во многих обсуждениях и реализациях абстрактного типа данных list обход списка клиентским кодом не считается базовой операцией, поэтому вопроса о концепции итератора никогда не возни- кает. Наконец, если мы начнем свой среди алгоритмов, то вряд ли най- дем что-нибудь полезное. Алгоритмы, как правило, описывают слож- ный код, а код для создания итератора довольно прост, как мы вскоре увидим. Поэтому в данном случае библиотека классов была самым бы- стрым путем к месту назначения, за которым следуют шаблоны. Одна- ко, как правило, вы должны учитывать все типы компонентов при по- иске того, который может оказаться для вас полезным.
Применение компонента
Теперь мы знаем, что собираемся создать итератор для класса stu- dentCollection
, однако все, что нам показал класс стандартной би- блиотеки list, — это то, как методы итератора работают вовне.
Решение задач с помощью повторного использования кода 219
Если бы мы застряли на этапе реализации, то могли бы проверить исходный код list и его классы-предки, однако, учитывая слож- ность чтения больших фрагментов незнакомого кода, это было бы крайней мерой. Вместо этого давайте просто подумаем над этим.
Используя предыдущий пример кода в качестве руководства, мож- но сказать, что итератор определяется четырьмя центральными операциями.
1. Метод в классе коллекции, предоставляющий итератор, кото- рый ссылается на первый элемент в коллекции. В классе list это был метод begin.
2. Механизм для проверки того, прошел ли итератор последний элемент в коллекции. В предыдущем примере это был метод под названием end в классе list, который создал специальный объ- ект итератора для тестирования.
3. Метод в классе итератора, который перемещает итератор, что- бы он ссылался на следующий элемент в коллекции. В предыду- щем примере это был перегруженный оператор ++.
4. Метод в классе итератора, который возвращает элемент коллек- ции, на который в данный момент ссылается итератор. В преды- дущем примере это был перегруженный префиксный оператор*.
В плане написания кода здесь нет ничего сложного. Нужно лишь расставить все по своим местам. Из приведенных выше описаний следует, что наш итератор, который назовем scIterator, должен хранить ссылку на элемент в коллекции studentCollection и должен иметь возможность перейти к следующему элементу. Таким образом, итератор должен хранить указатель на studentNode. Это позволит ему возвратить содержащуюся внутри запись studentRecord, а также перейти к следующему studentNode. Поэтому приватный раздел клас- са итератора будет содержать следую щий член данных: studentCollection::studentNode * current;
У нас сразу возникает проблема. Тип studentNode объявляется в приватном разделе коллекции studentCollection, поэтому приве- денная выше строка не сработает. Нашей первой мыслью являет- ся то, что, возможно, studentNode не должен быть приватным, од- нако этот ответ неверен. Приватность — неотъемлемое свойство типа узла, поскольку мы не хотим, чтобы случайный клиентский код зависел от конкретной реализации типа узла, тем самым созда- вая код, в котором может произойти сбой при изменении нашего класса. Тем не менее мы должны предоставить итератору scItera- tor доступ к нашему приватному типу. Мы делаем это с помощью объявления friend. В общедоступном разделе studentCollection добавляем: friend class scIterator;
220 Глава 7
Теперь scIterator может получить доступ к приватным объявле- ниям внутри studentCollection, включая объявление для student-
Node
. Мы также можем объявить несколько конструкторов: scIterator::scIterator() {
current = NULL;
}
scIterator::scIterator(studentCollection::studentNode * initial) {
current = initial;
}
Давайте на секунду перейдем к studentCollection и напишем наш метод begin, возвращающий итератор, который ссылается на пер- вый элемент в нашей коллекции. Следуя схеме именования, которую я использовал в этой книге, данный метод должен иметь в качестве имени существительное, например, rstItemIterator: scIterator studentCollection:: rstItemIterator() {
return scIterator(_listHead);
}
Как видите, все, что нам нужно сделать, — это поместить указа- тель на головной элемент связного списка в объект scIterator и воз- вратить его. Если вы похожи на меня, то мельтешащие указатели мо- гут вас немного нервировать, однако обратите внимание на то, что scIterator будет просто держаться за ссылку на элемент в списке studentCollection
. Он не будет выделять собственную память, поэ- тому нам не нужно беспокоиться о глубоких копиях и перегружен- ных операторах присваивания.
Вернемся к scIterator и напишем другие наши методы. Нам нужен метод для перехода итератора к следующему элементу, а также метод для определения того, достигли ли мы конца коллек- ции. Мы должны думать обо всем этом одновременно. При пере- мещении итератора нужно знать, какое значение должен иметь итератор при выходе за пределы последнего узла в списке. Если мы не делаем ничего особенного, итератор, естественно, получит значение NULL, так что это будет самое простое для использования значение. Обратите внимание на то, что мы инициализировали итератор значением NULL в конструкторе по умолчанию, поэто- му, когда мы используем NULL для обозначения конца коллекции, между этими двумя состояниями теряется всякое различие, одна- ко в случае данной задачи это не проблема. Ниже показан код для методов:
X void scIterator::advance() {
Y if (current != NULL)
Z current = current->next;
}
[ bool scIterator::pastEnd() {
return current == NULL;
}
Решение задач с помощью повторного использования кода 221
Помните, что мы просто используем концепцию итератора для решения исходной задачи. Мы не пытаемся дублировать точную спецификацию итератора стандартной библиотеки шаблонов C++, поэтому нам необязательно использовать тот же самый интерфейс.
В данном случае вместо перегрузки оператора ++ я применяю метод advance
X
, который проверяет, что указатель current не имеет зна- чения NULL
Y
, прежде чем перемещать его к следующему узлу
Z
. Точ- но так же я считаю громоздким создание специального «конечного» итератора для сравнения, поэтому я просто использую метод bool под названием pastEnd
[
, который определяет, закончились ли у нас узлы.
Наконец, нам нужен способ получения объекта studentRecord, на который мы в данный момент ссылаемся: studentRecord scIterator::student() {
X if (current == NULL) {
studentRecord dummyRecord(-1, -1, "");
return dummyRecord;
Y } else {
return current->studentData;
}
}
Как и ранее, в целях безопасности, если наш указатель имеет зна- чение NULL, мы создаем и возвращаем фиктивную запись
X
. В про- тивном случае мы возвращаем запись, на которую в данный момент ссылаемся
Y
. Это завершает реализацию концепции итератора с на- шим классом studentCollection. Для ясности далее приведено пол- ное объявление класса scIterator: class scIterator {
public:
scIterator();
scIterator(studentCollection::studentNode * initial);
void advance();
bool pastEnd();
studentRecord student();
private:
studentCollection::studentNode * current;
};
Теперь, когда код готов, мы можем протестировать его с помо- щью пробного обхода. Давайте реализуем процесс вычисления сред- ней оценки для сравнения: scIterator iter;
int gradeTotal = 0;
int numRecords = 0;
X iter = sc. rstItemIterator();
Y while (!iter.pastEnd()) {
numRecords++;
Z gradeTotal += iter.student().grade();
[ iter.advance();
}
double average = (double) gradeTotal / numRecords;
222 Глава 7
В этом листинге используются все наши методы, имеющие от- ношение к итератору, поэтому он представляет собой хороший тест для нашего кода. Мы вызываем rstItemIterator для инициализа- ции объекта scIterator
X
. Мы вызываем метод pastEnd в качестве те- ста на завершение цикла
Y
. Мы вызываем метод объекта итератора student для получения текущей записи studentRecord, чтобы иметь возможность извлечь оценку
Z
. Наконец, для перемещения итера- тора на следующую запись мы вызываем метод advance
[
. Когда этот код работает, мы можем быть в достаточной степени уверенными в том, что мы правильно реализовали различные методы и, более того, четко усвоили концепцию итератора.
Анализ эффективного решения задачи с обходом
Как и прежде, если код работает, это не значит, что мы не можем научиться на нем чему-то еще. Мы должны внимательно посмо- треть, что сделали, проанализировать положительные и отрица- тельные последствия, а также рассмотреть возможность расши- рения базовой идеи, которую только что реализовали. В данном случае мы можем сказать, что концепция итератора определенно решает исходную проблему неэффективного обхода нашей кол- лекции клиентским кодом, и после ее реализации использова- ние итератора является элегантным и легко читаемым решением.
С другой стороны, нельзя отрицать, что неэффективный подход, основанный на методе recordAt, был намного более простым в на- писании. При решении вопроса о ценности реализации итерато- ра для конкретной ситуации мы должны спросить себя, как часто будут иметь место обходы, сколько элементов, как правило, будет содержаться в нашем списке и т.д. Если обходы редки, а список мал, то неэффективность, вероятно, не будет иметь значения, од- нако если мы ожидаем увеличения списка или не можем гаранти- ровать, что этого не произойдет, то нам может потребоваться ите- ратор.
Конечно, если бы мы решили использовать объект list из стан- дартной библиотеки шаблонов, нам больше не пришлось бы беспоко- иться о сложности реализации итератора, поскольку не нужно было бы самим его реализовывать. В следующий раз, когда возникнет по- добная ситуация, мы сможем использовать класс list без ощущения того, что мы обманываем себя или настраиваемся на трудности в бу- дущем, поскольку мы изучили списки и итераторы достаточно, что- бы понимать, что происходит за кулисами, даже если мы никогда не рассматривали фактический исходный код.
Заходя еще дальше, мы можем подумать о более широком при- менении итераторов и об их возможных ограничениях. Например, предположим, что нам понадобился итератор, который мог бы эф- фективно перемещаться не только к следующему элементу нашей studentCollection
, но и к предыдущему. Теперь, когда мы знаем, как работает итератор, понимаем, что не можем решить эту зада-
По завершении цикла, если был достигнут конец списка, мы создаем и возвращаем фиктивную запись
Y
или возвращаем запись в указан- ной позиции
Z
. Проблема в том, что мы производим обход для на- хождения только одной записи ученика. Этот обход необязательно полон, поскольку мы остановимся, когда достигнем желаемой пози- ции, но тем не менее это обход. Предположим, что клиентский код пытается усреднить оценки учащихся: int gradeTotal = 0;
for (int recNum = 1; recNum <= numRecords; recNum++) {
studentRecord temp = sc.recordAt(recNum);
gradeTotal += temp.grade();
}
double average = (double) gradeTotal / numRecords;
Для этого сегмента кода предположим, что sc — это ранее объяв- ленная и заполненная коллекция studentCollection, а recNum пред- ставляет собой переменную типа int, в которой хранится количе- ство записей. Предположим, что значение recNum равно 100. При поверхностном взгляде на этот код вам может показаться, что вы- числение среднего значения требует всего 100 запусков цикла, одна- ко, поскольку каждый вызов recordAt сам по себе является частич- ным обходом списка, этот код предполагает 100 обходов, каждый из которых будет включать около 50 запусков цикла для среднего слу- чая. Таким образом, вместо 100 шагов, что считалось бы эффектив- ным, для этого может потребоваться около 5000 шагов, что было бы очень неэффективно.
Когда следует искать компонент
Теперь мы столкнулись с реальной проблемой. Предоставить клиен- ту доступ к членам коллекции для совершения обхода легко; обеспе- чить эффективность такого доступа сложно. Разумеется, мы могли бы решить эту задачу, используя только собственные возможности, одна- ко мы могли бы достичь решения намного быстрее с помощью ком- понента. Первым шагом при поиске неизвестного компонента, ко- торый может помочь нам решить задачу, является предположение о том, что такой компонент на самом деле существует. Иными словами, вы не найдете компонент, если не начнете его искать. Поэтому, чтобы извлечь из компонентов максимальную пользу, вам нужно уметь опре- делять ситуации, где они могут пригодиться. Если вы застрянете на каком-то аспекте проблемы, попробуйте сделать следующее.
1. Сформулируйте проблему в общем виде.
2. Спросите себя: может ли это быть распространенной пробле- мой?
Первый шаг важен, потому что если мы сформулируем задачу так: «Позволить клиентскому коду эффективно вычислять среднюю оценку учеников в связном списке записей, инкапсулированных в классе», то это покажется характерным для нашей ситуации. Одна-
Решение задач с помощью повторного использования кода 217
ко если мы сформулируем задачу так: «Позволить клиентскому коду эффективно обходить связный список без предоставления прямого доступа к указателям списка», то мы начнем понимать, что это мо- жет быть распространенной проблемой. Поскольку программы ча- сто хранят связные списки и другие структуры с последовательным доступом в классах, мы можем предположить, что другие програм- мисты должны были выяснить, как можно обеспечить эффективный доступ к каждому элементу структуры.
Нахождение компонента
Теперь, когда мы готовы искать, пришло время найти наш компо- нент. Чтобы все было ясно, давайте переформулируем исходную за- дачу программирования как исследовательскую проблему: «Найдите компонент, который можно использовать для изменения класса stu- dentCollection таким образом, чтобы клиентский код мог эффектив- но обходить внутренний список». Как мы можем решить эту задачу?
Мы могли бы начать с рассмотрения любого из наших типов ком- понентов: шаблонов, алгоритмов, абстрактных типов данных или библио тек.
Предположим, что мы начали с рассмотрения стандартных биб- лиотек C++. Мы не обязательно будем искать класс для «включения» в решение, вместо этого мы могли бы поискать идеи в библиотеке клас- сов, напоминающей класс studentCollection. Это подразумевает при- менение стратегии поиска аналогии, которую мы использовали для решения задач по программированию. Если мы найдем класс с анало- гичной проблемой, то сможем воспользоваться его аналогичным ре- шением. В ходе нашего предыдущего рассмотрения библиотеки C++ мы познакомились с такими его контейнерными классами, как vec- tor
, и нам следует искать контейнерный класс, который больше всего похож на класс studentCollection. Если мы обратимся к нашему лю- бимому ресурсу, посвященному C++, будь то книга или интернет-сайт, и рассмотрим контейнерные классы C++, мы увидим там «контейнер последовательности» под названием list, который соответствует на- шему запросу. Позволяет ли класс list клиентскому коду совершать эффективный обход? Да, используя объект, известный как итератор.
Мы видим, что класс list предусматривает методы begin и end, созда- ющие итераторы, которые являются объектами, которые могут ссы- латься на определенный элемент в списке и инкрементироваться, чтобы итератор мог сослаться на следующий объект в списке. Если intList представляет собой list
while (iter != intList.end()) {
cout << *iter << "\n";
iter++;
}
218 Глава 7
Благодаря использованию итератора класс list решил пробле- му, предоставив клиентскому коду механизм для эффективного об- хода списка. Сейчас мы можем подумать о том, чтобы поместить сам класс list в класс studentCollection, заменив наш самодельный связный список. Затем мы могли бы создать методы begin и end для нашего класса, которые обернули бы те же методы из встроенного объекта списка, и проблема была бы решена. Однако это напрямую связано с проблемой хорошего или плохого повторного использо- вания кода. Когда мы полностью поймем концепцию итератора и сможем самостоятельно воспроизвести ее в собственном коде, включение в код существующего класса из стандартной библиотеки шаблонов будет хорошим, а вероятно, и лучшим вариантом. Если мы не сможем этого сделать, то использование класса list станет обход- ным путем, который не поможет нам вырасти в области программи- рования. Иногда, конечно, нужно использовать компоненты, кото- рые мы не можем воспроизвести сами, однако если мы привыкнем к зависимости от других программистов при решении задач, то риску- ем никогда не научиться решать задачи самостоятельно.
Итак, давайте самостоятельно реализуем итератор. Прежде чем мы это сделаем, давайте кратко рассмотрим другие способы, с помощью которых мы могли бы прийти к тому же самому результату. Мы нача- ли поиск со стандартных библиотек шаблонов, однако могли бы начать искать в другом месте. Например, мы могли бы просмотреть список распространенных шаблонов проектирования. Под заголовком «пове- денческие шаблоны» мы бы нашли шаблон iterator, в котором клиенту предоставляется последовательный доступ к коллекции элементов без раскрытия базовой структуры этой коллекции. Это именно то, что нуж- но, однако мы могли бы обнаружить это решение только, осуществив поиск в списке шаблонов или вспомнив о том, что оно нам уже попа- далось в ходе предыдущего исследования шаблонов. Мы могли бы на- чать поиск с абстрактных типов данных, потому что список вообще и
связный список в частности — распространенные абстрактные типы дан- ных. Тем не менее во многих обсуждениях и реализациях абстрактного типа данных list обход списка клиентским кодом не считается базовой операцией, поэтому вопроса о концепции итератора никогда не возни- кает. Наконец, если мы начнем свой среди алгоритмов, то вряд ли най- дем что-нибудь полезное. Алгоритмы, как правило, описывают слож- ный код, а код для создания итератора довольно прост, как мы вскоре увидим. Поэтому в данном случае библиотека классов была самым бы- стрым путем к месту назначения, за которым следуют шаблоны. Одна- ко, как правило, вы должны учитывать все типы компонентов при по- иске того, который может оказаться для вас полезным.
Применение компонента
Теперь мы знаем, что собираемся создать итератор для класса stu- dentCollection
, однако все, что нам показал класс стандартной би- блиотеки list, — это то, как методы итератора работают вовне.
Решение задач с помощью повторного использования кода 219
Если бы мы застряли на этапе реализации, то могли бы проверить исходный код list и его классы-предки, однако, учитывая слож- ность чтения больших фрагментов незнакомого кода, это было бы крайней мерой. Вместо этого давайте просто подумаем над этим.
Используя предыдущий пример кода в качестве руководства, мож- но сказать, что итератор определяется четырьмя центральными операциями.
1. Метод в классе коллекции, предоставляющий итератор, кото- рый ссылается на первый элемент в коллекции. В классе list это был метод begin.
2. Механизм для проверки того, прошел ли итератор последний элемент в коллекции. В предыдущем примере это был метод под названием end в классе list, который создал специальный объ- ект итератора для тестирования.
3. Метод в классе итератора, который перемещает итератор, что- бы он ссылался на следующий элемент в коллекции. В предыду- щем примере это был перегруженный оператор ++.
4. Метод в классе итератора, который возвращает элемент коллек- ции, на который в данный момент ссылается итератор. В преды- дущем примере это был перегруженный префиксный оператор*.
В плане написания кода здесь нет ничего сложного. Нужно лишь расставить все по своим местам. Из приведенных выше описаний следует, что наш итератор, который назовем scIterator, должен хранить ссылку на элемент в коллекции studentCollection и должен иметь возможность перейти к следующему элементу. Таким образом, итератор должен хранить указатель на studentNode. Это позволит ему возвратить содержащуюся внутри запись studentRecord, а также перейти к следующему studentNode. Поэтому приватный раздел клас- са итератора будет содержать следую щий член данных: studentCollection::studentNode * current;
У нас сразу возникает проблема. Тип studentNode объявляется в приватном разделе коллекции studentCollection, поэтому приве- денная выше строка не сработает. Нашей первой мыслью являет- ся то, что, возможно, studentNode не должен быть приватным, од- нако этот ответ неверен. Приватность — неотъемлемое свойство типа узла, поскольку мы не хотим, чтобы случайный клиентский код зависел от конкретной реализации типа узла, тем самым созда- вая код, в котором может произойти сбой при изменении нашего класса. Тем не менее мы должны предоставить итератору scItera- tor доступ к нашему приватному типу. Мы делаем это с помощью объявления friend. В общедоступном разделе studentCollection добавляем: friend class scIterator;
220 Глава 7
Теперь scIterator может получить доступ к приватным объявле- ниям внутри studentCollection, включая объявление для student-
Node
. Мы также можем объявить несколько конструкторов: scIterator::scIterator() {
current = NULL;
}
scIterator::scIterator(studentCollection::studentNode * initial) {
current = initial;
}
Давайте на секунду перейдем к studentCollection и напишем наш метод begin, возвращающий итератор, который ссылается на пер- вый элемент в нашей коллекции. Следуя схеме именования, которую я использовал в этой книге, данный метод должен иметь в качестве имени существительное, например, rstItemIterator: scIterator studentCollection:: rstItemIterator() {
return scIterator(_listHead);
}
Как видите, все, что нам нужно сделать, — это поместить указа- тель на головной элемент связного списка в объект scIterator и воз- вратить его. Если вы похожи на меня, то мельтешащие указатели мо- гут вас немного нервировать, однако обратите внимание на то, что scIterator будет просто держаться за ссылку на элемент в списке studentCollection
. Он не будет выделять собственную память, поэ- тому нам не нужно беспокоиться о глубоких копиях и перегружен- ных операторах присваивания.
Вернемся к scIterator и напишем другие наши методы. Нам нужен метод для перехода итератора к следующему элементу, а также метод для определения того, достигли ли мы конца коллек- ции. Мы должны думать обо всем этом одновременно. При пере- мещении итератора нужно знать, какое значение должен иметь итератор при выходе за пределы последнего узла в списке. Если мы не делаем ничего особенного, итератор, естественно, получит значение NULL, так что это будет самое простое для использования значение. Обратите внимание на то, что мы инициализировали итератор значением NULL в конструкторе по умолчанию, поэто- му, когда мы используем NULL для обозначения конца коллекции, между этими двумя состояниями теряется всякое различие, одна- ко в случае данной задачи это не проблема. Ниже показан код для методов:
X void scIterator::advance() {
Y if (current != NULL)
Z current = current->next;
}
[ bool scIterator::pastEnd() {
return current == NULL;
}
Решение задач с помощью повторного использования кода 221
Помните, что мы просто используем концепцию итератора для решения исходной задачи. Мы не пытаемся дублировать точную спецификацию итератора стандартной библиотеки шаблонов C++, поэтому нам необязательно использовать тот же самый интерфейс.
В данном случае вместо перегрузки оператора ++ я применяю метод advance
X
, который проверяет, что указатель current не имеет зна- чения NULL
Y
, прежде чем перемещать его к следующему узлу
Z
. Точ- но так же я считаю громоздким создание специального «конечного» итератора для сравнения, поэтому я просто использую метод bool под названием pastEnd
[
, который определяет, закончились ли у нас узлы.
Наконец, нам нужен способ получения объекта studentRecord, на который мы в данный момент ссылаемся: studentRecord scIterator::student() {
X if (current == NULL) {
studentRecord dummyRecord(-1, -1, "");
return dummyRecord;
Y } else {
return current->studentData;
}
}
Как и ранее, в целях безопасности, если наш указатель имеет зна- чение NULL, мы создаем и возвращаем фиктивную запись
X
. В про- тивном случае мы возвращаем запись, на которую в данный момент ссылаемся
Y
. Это завершает реализацию концепции итератора с на- шим классом studentCollection. Для ясности далее приведено пол- ное объявление класса scIterator: class scIterator {
public:
scIterator();
scIterator(studentCollection::studentNode * initial);
void advance();
bool pastEnd();
studentRecord student();
private:
studentCollection::studentNode * current;
};
Теперь, когда код готов, мы можем протестировать его с помо- щью пробного обхода. Давайте реализуем процесс вычисления сред- ней оценки для сравнения: scIterator iter;
int gradeTotal = 0;
int numRecords = 0;
X iter = sc. rstItemIterator();
Y while (!iter.pastEnd()) {
numRecords++;
Z gradeTotal += iter.student().grade();
[ iter.advance();
}
double average = (double) gradeTotal / numRecords;
222 Глава 7
В этом листинге используются все наши методы, имеющие от- ношение к итератору, поэтому он представляет собой хороший тест для нашего кода. Мы вызываем rstItemIterator для инициализа- ции объекта scIterator
X
. Мы вызываем метод pastEnd в качестве те- ста на завершение цикла
Y
. Мы вызываем метод объекта итератора student для получения текущей записи studentRecord, чтобы иметь возможность извлечь оценку
Z
. Наконец, для перемещения итера- тора на следующую запись мы вызываем метод advance
[
. Когда этот код работает, мы можем быть в достаточной степени уверенными в том, что мы правильно реализовали различные методы и, более того, четко усвоили концепцию итератора.
Анализ эффективного решения задачи с обходом
Как и прежде, если код работает, это не значит, что мы не можем научиться на нем чему-то еще. Мы должны внимательно посмо- треть, что сделали, проанализировать положительные и отрица- тельные последствия, а также рассмотреть возможность расши- рения базовой идеи, которую только что реализовали. В данном случае мы можем сказать, что концепция итератора определенно решает исходную проблему неэффективного обхода нашей кол- лекции клиентским кодом, и после ее реализации использова- ние итератора является элегантным и легко читаемым решением.
С другой стороны, нельзя отрицать, что неэффективный подход, основанный на методе recordAt, был намного более простым в на- писании. При решении вопроса о ценности реализации итерато- ра для конкретной ситуации мы должны спросить себя, как часто будут иметь место обходы, сколько элементов, как правило, будет содержаться в нашем списке и т.д. Если обходы редки, а список мал, то неэффективность, вероятно, не будет иметь значения, од- нако если мы ожидаем увеличения списка или не можем гаранти- ровать, что этого не произойдет, то нам может потребоваться ите- ратор.
Конечно, если бы мы решили использовать объект list из стан- дартной библиотеки шаблонов, нам больше не пришлось бы беспоко- иться о сложности реализации итератора, поскольку не нужно было бы самим его реализовывать. В следующий раз, когда возникнет по- добная ситуация, мы сможем использовать класс list без ощущения того, что мы обманываем себя или настраиваемся на трудности в бу- дущем, поскольку мы изучили списки и итераторы достаточно, что- бы понимать, что происходит за кулисами, даже если мы никогда не рассматривали фактический исходный код.
Заходя еще дальше, мы можем подумать о более широком при- менении итераторов и об их возможных ограничениях. Например, предположим, что нам понадобился итератор, который мог бы эф- фективно перемещаться не только к следующему элементу нашей studentCollection
, но и к предыдущему. Теперь, когда мы знаем, как работает итератор, понимаем, что не можем решить эту зада-