Б.10.4). Создайте класс vector так, как описано в конце раздела 19.4, для работы с несколькими тестовыми примерами.
9. Повторите реализацию функции vector::operator=() (см. раздел 19.2.5), используя класс allocator (см. раздел 19.3.6) для управления памятью.
10. Реализуйте простой класс auto_ptr, содержащий только конструктор, деструктор, операторы –> и *, а также функцию release(). В частности, не пытайтесь реализовать присваивание или копирующий конструктор.
11. Разработайте и реализуйте класс counted_ptr<T>, владеющий указателем на объект типа T, и указатель, подсчитывающий количество ссылок (переменная типа int), общий для всех указателей, с подсчетом ссылок на один и тот же объект типа T. Счетчик ссылок должен содержать количество указателей, ссылающихся на данный объект типа T. Конструктор класса counted_ptr должен размещать в свободной памяти объект типа T и счетчик ссылок. Присвойте объекту класса counted_ptr начальное значение типа T. После уничтожения последнего объекта класса counted_ptr для класса T его деструктор должен удалить объект класса T. Предусмотрите в классе counted_ptr операции, позволяющие использовать его как указатель. Это пример так называемого “интеллектуального указателя”, который используется для того, чтобы гарантировать, что объект не будет уничтожен, пока последний пользователь не прекратит на него ссылаться. Напишите набор тестов для класса counted_ptr, используя его объекты в качестве аргументов при вызове функций, в качестве элементов контейнера и т.д.
12. Определите класс File_handle, конструктор которого получает аргумент типа string (имя файла) и открывает файл, а деструктор закрывает файл.
13. Напишите класс Tracer, в котором конструктор вводит, а деструктор выводит строки. Аргументами конструктора должны быть строки. Используйте этот пример для демонстрации того, как работают объекты, соответствующие принципу RAII (например, поэкспериментируйте с объектами класса Tracer, играющими роль локальных объектов, объектов-членов класса, глобальных объектов, объектов, размещенных с помощью оператора new, и т.д.). Затем добавьте копирующий конструктор и копирующее присваивание, чтобы можно было увидеть поведение объектов класса Tracer в процессе копирования.
14. Разработайте графический пользовательский интерфейс и средства вывода для игры “Охота на Вампуса” (см. главу 18). Предусмотрите ввод данных из окна редактирования и выведите на экран карту части пещеры, известной игроку.
15. Модифицируйте программу из предыдущего упражнения, чтобы дать пользователю возможность помечать комнаты, основываясь на знаниях и догадках, таких как “могут быть летучие мыши” и “бездонная пропасть”.
16. Иногда желательно, чтобы пустой вектор был как можно более маленьким. Например, можно интенсивно использовать класс vector<vector<vector<int>>>, в котором большинство векторов пусто. Определите вектор так, чтобы выполнялось условие sizeof(vector<int>)==sizeof(int*), т.е. чтобы класс вектора состоял только из указателя на массив элементов, количества элементов и указателя space.
Послесловие
Шаблоны и исключения представляют собой весьма мощные языковые конструкции. Они поддерживают весьма гибкие технологии программирования — в основном благодаря разделению ответственности, т.е. возможности решать по одной проблеме в каждый отдельный момент времени. Например, используя шаблоны, мы можем определить контейнер, такой как vector, отделив его от определения типа элементов. Аналогично можно написать код, идентифицирующий ошибки и выдающий сообщения о них, отдельно от кода, предназначенного для их обработки. Третья основная тема, связанная с изменением размера вектора, относительно проста: функции push_back(), resize() и reserve() позволяют отделить определение вектора от спецификации его размера.
Глава 20
Контейнеры и итераторы
“Пишите программы, которые делают что-то одно
и делают это хорошо. Пишите программы,
чтобы работать вместе”.
Дуг Мак-Илрой (Doug McIlroy)
Эта и следующая главы посвящены библиотеке STL — части стандартной библиотеки языка С++, содержащей контейнеры и алгоритмы. Библиотека STL — это масштабируемый каркас для обработки данных в программе на языке С++. Сначала мы рассмотрим простой пример, а потом изложим общие идеи и основные концепции. Мы обсудим понятие итерации, манипуляции со связанными списками, а также контейнеры из библиотеки STL. Связь между контейнерами (данными) и алгоритмами (обработкой) обеспечивается последовательностью и итераторами. В настоящей главе изложены основы для универсальных, эффективных и полезных алгоритмов, описанных в следующей главе. В качестве примера простого приложения рассматривается редактирование текста.
20.1. Хранение и обработка данных
Перед тем как перейти к исследованию крупных коллекций данных, рассмотрим простой пример, иллюстрирующий способы решения большого класса задач, связанных с обработкой данных. Представим себе, что Джек и Джилл измеряют скорость автомобилей, записывая их в виде чисел с плавающей точкой. Допустим, что Джек — программирует на языке С и хранит свои данные в массиве, а Джилл записывает свои измерения в объект класса vector. Мы хотели бы использовать их данные в своей программе. Как это сделать?
Потребуем, чтобы программы Джека и Джилл записывали значения в файл, чтобы мы могли считать их в своей программе. В этом случае мы не будем зависеть от выбора структур данных и интерфейсов, сделанных Джеком и Джилл. Довольно часто такая изоляция целиком оправданна. Для ее реализации в наших вычислениях можно использовать приемы ввода, описанные в главах 10 и 11, и класс vector<double>.
Однако что делать, если использовать файлы для решения нашей задачи слишком сложно? Допустим, что код для регистрации данных оформлен в виде функции, которая каждую секунду поставляет новый набор данных. В таком случае каждую секунду мы будем вызывать функции Джека и Джилл, чтобы получить данные для обработки.
double* get_from_jack(int* count); // Джек записывает числа
// типа double в массив и возвращает
// количество элементов в массиве *count
vector<double>* get_from_jill(); // Джилл заполняет вектор
void fct()
{
int jack_count = 0;
double* jack_data = get_from_jack(&jack_count);
vector<double>* jill_data = get_from_jill();
// ...обрабатываем...
delete[] jack_data;
delete jill_data;
}
Мы предполагаем, что эти данные хранятся в свободной памяти и их следует удалить после завершения обработки. Другое предположение заключается в том, что мы не можем переписать код, написанный Джеком и Джилл, или не хотим этого делать.
20.1.1. Работа с данными
Очевидно, что этот пример носит слишком упрощенный характер, но он похож на многие реальные задачи. Если мы сможем элегантно решить эту задачу, то сможем справиться с огромным множеством других задач программирования. В данной ситуации фундаментальная проблема заключается в том, что мы не можем повлиять на способ хранения данных, который выбрали поставщики. Наша задача состоит
