10. Проанализируйте решение задачи о палиндроме из раздела 18.6.2 на основе массива 10. Исправьте его так, чтобы можно было работать с длинными строками: 1) выдавайте сообщение, если введенная строка оказалась слишком длинной; 2) разрешите произвольно длинные строки. Прокомментируйте сложность обеих версий.

11. Разберитесь, что собой представляет список с пропусками (skip list), и реализуйте эту разновидность списка. Это не простое упражнение.

12. Реализуйте версию игры “Охота на Вампуса” (или просто “Вамп”). Это простая компьютерная (не графическая) игра, изобретенная Грегори Йобом (Gregory Yob). Цель этой игры — найти довольно смышленого монстра, прячущегося в темном пещерном лабиринте. Ваша задача — убить вампуса с помощью лука и стрел. Кроме вампуса, пещера таит еще две опасности: бездонные ямы и гигантские летучие мыши. Если вы входите в комнату с бездонной ямой, то игра для вас закончена. Если вы входите в комнату с летучей мышью, то она вас хватает и перебрасывает в другую комнату. Если же вы входите в комнату с вампусом или он входит в комнату, где находитесь вы, он вас съедает. Входя в комнату, вы должны получить предупреждение о грозящей опасности.

  “Я чувствую запах вампуса” — значит, он в соседней комнате.

  “Я чувствую ветерок” — значит, в соседней комнате яма.

  “Я слышу летучую мышь” — значит, в соседней комнате живет летучая мышь.

Для вашего удобства комнаты пронумерованы. Каждая комната соединена туннелями с тремя другими. Когда вы входите в комнату, то получаете сообщение, например: “Вы в комнате номер 12; отсюда идут туннели в комнаты 1, 13 и 4; идти или стрелять?” Возможные ответы:

(“Переход в комнату номер 13”) и (“Стрелять через комнаты с номерами 13, 4 и 3”). Стрела может пролететь через три комнаты. В начале игры у вас есть пять стрел. Загвоздка со стрельбой заключается в том, что вы можете разбудить вампуса и он войдет в комнату, соседнюю с той, где он спал, — она может оказаться вашей комнатой.

Вероятно, самой сложной частью этого упражнения является программирование пещеры и выбор комнат, связанных с другими комнатами. Возможно, вы захотите использовать датчик случайных чисел (например, функцию

из библиотеки , чтобы при разных запусках программы использовались разные пещеры и разное расположение летучих мышей и вампуса. Подсказка: используйте режим отладки для проверки состояния лабиринта.

Послесловие

Стандартный класс vector основан на средствах низкоуровневого управления памятью, таких как указатели и массивы. Его главное предназначение — помочь программисту избежать сложностей, сопряженных с этими средствами управления памятью. Разрабатывая любой класс, вы должны предусмотреть инициализацию, копирование и уничтожение его объектов.

Глава 19

Векторы, шаблоны и исключения

В этой главе мы завершим изучение вопросов проектирования и реализации наиболее известного и полезного контейнера из библиотеки STL: класса

. Мы покажем, как реализовать контейнеры с переменным количеством элементов, как описать контейнеры, в которых тип является параметром, а также продемонстрируем, как обрабатывать ошибки, связанные с выходом за пределы допустимого диапазона. Как обычно, описанные здесь приемы будут носить универсальный характер, выходя далеко за рамки класса и даже реализации контейнеров. По существу, мы покажем, как безопасно работать с переменным объемом данных разных типов. Кроме того, в примерах проектирования постараемся учесть конкретные реалии. Наша технология программирования основана на шаблонах и исключениях, поэтому мы покажем, как определить шаблоны, и продемонстрируем основные способы управления ресурсами, играющими ключевую роль в эффективной работе с исключениями.

19.1. Проблемы

В конце главы 18 наша разработка класса

достигла этапа, на котором мы могли выполнять следующие операции.

• Создавать объекты класса

, элементами которого являются числа с плавающей точкой двойной точности с любым количеством элементов.

• Копировать объекты класса

с помощью присваивания и инициализации.

• Корректно освобождать память, занятую объектом класса

, когда он выходит за пределы области видимости.

• Обращаться к элементам объекта класса

, используя обычные индексные обозначения (как в правой, так и в левой части оператора присваивания).

Все это хорошо и полезно, но, для того чтобы выйти на ожидаемый уровень сложности (ориентируясь на сложность стандартного библиотечного класса

), мы должны разрешить еще несколько проблем.

• Как изменить размер объекта класса

(изменить количество его элементов)?

• Как перехватить и обработать ошибку, связанную с выходом за пределы объекта класса

?

• Как задать тип элементов в объекте класса

в качестве аргумента?

Например, как определить класс

так, чтобы стало возможным написать следующий код:

Очевидно, что такие операции над векторами очень полезны, но почему это так важно с программистской точки зрения? Почему это достойно включения в стандартный набор приемов программирования? Дело в том, что эти операции обеспечивают двойную гибкость. У нас есть одна сущность, объект класса

, которую мы можем изменить двумя способами.

• Изменить количество элементов.

• Изменить тип элементов.

Эти виды изменчивости весьма полезны и носят фундаментальный характер. Мы всегда собираем данные. Окидывая взглядом свой письменный стол, я вижу груду банковских счетов, счета за пользование кредитными карточками и телефонные разговоры. Каждый из этих счетов по существу представляет собой список строк, содержащих информацию разного типа: строки букв и чисел. Передо мной лежит телефон; в нем хранится список имен и телефонных номеров. В книжных шкафах на полках стоят книги. Наши программы схожи с ними: в них описаны контейнеры, состоящие из элементов разных типов. Существуют разные контейнеры (класс

просто используется чаще других), содержащие разную информацию: телефонные номера, имена, суммы банковских операций и документы. По существу, все, что лежит на моем столе, было создано с помощью каких-то компьютерных программ.