- •Содержание
- •Благодарности
- •Как читать эту книгу
- •Несколько слов о стиле программирования
- •Переменные и константы
- •const
- •Стековые и динамические объекты
- •Области действия и функции
- •Области действия
- •Перегрузка
- •Видимость
- •Типы и операторы
- •Конструкторы
- •Деструкторы
- •Присваивание
- •Перегрузка операторов
- •Что такое шаблоны и зачем они нужны?
- •Проблемы
- •Обходные решения
- •Синтаксис шаблонов
- •Параметризованные типы
- •Параметризованные функции
- •Параметризованные функции классов
- •Передача параметра
- •Шаблоны с несколькими параметрами
- •Долой вложенные параметризованные типы!
- •Наследование
- •Комбинации простых и параметризованных типов
- •Небезопасные типы в открытых базовых классах
- •Небезопасные типы в закрытых базовых классах
- •Небезопасные типы в переменных класса
- •Глава 4. Исключения
- •Обработка исключений в стандарте ANSI
- •Синтаксис инициирования исключений
- •Синтаксис перехвата исключений
- •Конструкторы и деструкторы
- •Нестандартная обработка исключений
- •Условные обозначения
- •Глава 5. Умные указатели
- •Глупые указатели
- •Умные указатели как идиома
- •Оператор ->
- •Параметризованные умные указатели
- •Иерархия умных указателей
- •Арифметические операции с указателями
- •Во что обходится умный указатель?
- •Применения
- •Разыменование значения NULL
- •Отладка и трассировка
- •Кэширование
- •Семантика ведущих указателей
- •Конструирование
- •Уничтожение
- •Копирование
- •Присваивание
- •Прототип шаблона ведущего указателя
- •Дескрипторы в C++
- •Что же получается?
- •Подсчет объектов
- •Указатели только для чтения
- •Указатели для чтения/записи
- •Интерфейсные указатели
- •Дублирование интерфейса
- •Маскировка указываемого объекта
- •Изменение интерфейса
- •Грани
- •Преобразование указываемого объекта в грань
- •Кристаллы
- •Вариации на тему граней
- •Инкапсуляция указываемого объекта
- •Проверка граней
- •Обеспечение согласованности
- •Грани и ведущие указатели
- •Переходные типы
- •Полиморфные указываемые объекты
- •Выбор типа указываемого объекта во время конструирования
- •Изменение указываемого объекта во время выполнения программы
- •Посредники
- •Функторы
- •Массивы и оператор []
- •Проверка границ и присваивание
- •Оператор [] с нецелыми аргументами
- •Имитация многомерных массивов
- •Множественные перегрузки оператора []
- •Виртуальный оператор []
- •Курсоры
- •Простой класс разреженного массива
- •Курсоры и разреженные массивы
- •Операторы преобразования и оператор ->
- •Итераторы
- •Активные итераторы
- •Пассивные итераторы
- •Что лучше?
- •Убогие, но распространенные варианты
- •Лучшие варианты
- •Итератор абстрактного массива
- •Операторы коллекций
- •Мудрые курсоры и надежность итераторов
- •Частные копии коллекций
- •Внутренние и внешние итераторы
- •Временная пометка
- •Пример
- •Тернистые пути дизайна
- •Транзакции
- •Отмена
- •Хватит?
- •Образы и указатели
- •Простой указатель образов
- •Стеки образов
- •Образы автоматических объектов
- •Образы указателей
- •Комбинации и вариации
- •Транзакции и отмена
- •Транзакции и блокировки
- •Класс ConstPtr
- •Класс LockPtr
- •Создание и уничтожение объектов
- •Упрощенное создание объектов
- •Отмена
- •Варианты
- •Вложенные блокировки
- •Взаимные блокировки и очереди
- •Многоуровневая отмена
- •Оптимизация объема
- •Несколько прощальных слов
- •Часть 3. Снова о типах
- •Гомоморфные иерархии классов
- •Взаимозаменяемость производных классов
- •Нормальное наследование
- •Инкапсуляция производных классов
- •Множественная передача
- •Двойная передача
- •Гетероморфная двойная передача
- •Передача более высокого порядка
- •Группировка передач и преобразования
- •Производящие функции
- •make-функции
- •Символические классы и перегруженные make-функции
- •Оптимизация с применением производящих функций
- •Локализованное использование производящих функций
- •Уничтожающие функции
- •Снова о двойной передаче: промежуточные базовые классы
- •Объекты классов
- •Информация о классе
- •Еще несколько слов об уничтожающих функциях
- •Определение класса по объекту
- •Представители
- •Основные концепции
- •Инкапсуляция указателей и указываемых объектов
- •Производящие функции
- •Ссылки на указатели
- •Неведущие указатели
- •Ведущие указатели
- •Снова о двойной передаче
- •Удвоенная двойная передача
- •Самомодификация и переходимость
- •Множественная двойная передача
- •Применение невидимых указателей
- •Кэширование
- •Распределенные объекты и посредники
- •Нетривиальные распределенные архитектуры
- •Часть 4. Управление памятью
- •Перегрузка операторов new и delete
- •Простой список свободной памяти
- •Наследование операторов new и delete
- •Аргументы оператора new
- •Конструирование с разделением фаз
- •Уничтожение с разделением фаз
- •Кто управляет выделением памяти?
- •Глобальное управление
- •Выделение и освобождение памяти в классах
- •Объекты классов и производящие функции
- •Управление памятью под руководством клиента
- •Управление памятью с применением ведущих указателей
- •Перспективы
- •Строительные блоки
- •Поблочное освобождение памяти
- •Скрытая информация
- •Подсчет ссылок
- •Базовый класс с подсчетом ссылок
- •Ведущие указатели с подсчетом ссылок
- •Дескрипторы с подсчетом ссылок
- •Трудности подсчета ссылок
- •Подсчет ссылок и ведущие указатели
- •Деление по классам
- •Деление по размеру
- •Деление по средствам доступа
- •Пространства стека и кучи
- •Поиск указателей
- •Мама, откуда берутся указатели?
- •Поиск указателей
- •Дескрипторы, повсюду дескрипторы
- •Общее описание архитектуры
- •Ведущие указатели
- •Вариации
- •Оптимизация в особых ситуациях
- •Алгоритм Бейкера
- •Пространства объектов
- •Последовательное копирование
- •Внешние объекты
- •Алгоритм Бейкера: уход и кормление в C++
- •Уплотнение на месте
- •Базовый класс VoidPtr
- •Пул ведущих указателей
- •Итератор ведущих указателей
- •Алгоритм уплотнения
- •Оптимизация
- •Перспективы
- •Глава 16. Сборка мусора
- •Доступность
- •Периметр
- •Внутри периметра
- •Анализ экземпляров
- •Перебор графа объектов
- •Сборка мусора по алгоритму Бейкера
- •Шаблон слабого дескриптора
- •Шаблон сильного дескриптора
- •Итераторы ведущих указателей
- •Перебор указателей
- •Оптимизация
- •Внешние объекты
- •Множественные пространства
- •Сборка мусора и уплотнение на месте
- •Нужно ли вызывать деструкторы?
- •Только для профессиональных каскадеров
- •Организация памяти
- •Поиск периметра
- •Перебор внутри периметра
- •Сборка мусора
- •Последовательная сборка мусора
- •Итоговые перспективы
124
bool operator>=(const Element*) const; // Истинно, если элемент
// принадлежит множеству
bool operator==(const Element*) const; // Истинно, если элемент
// является единственным элементом множества
};
Существует еще один вариант перегрузки оператора, о котором я вынужден упомянуть. Я так и не привык к операторам << и >> в качестве операторов «поразрядных сдвигов» в поток и из него, но поскольку они прочно внедрились в культуру С++, эту идиому приходится использовать хотя бы как базу для дальнейших расширений. Это приводит нас к дополнительному применению << и >> в контексте коллекций и итераторов:
•Оператор << может использоваться в итераторах как синоним функции Next().
•Оператор >> может использоваться как синоним более длинного оператора Set& operator|=(Element*) для «сдвига» новых элементов в коллекцию.
Вобоих идиомах оператор должен перегружаться в форме внешней функции, поскольку в левой части оператора находится Element*, а не Set. Идиома >> выглядит наиболее естественно для коллекций, сохраняющих исходный порядок вставки (например, списков).
Мы вернемся к этой теме в части 3 при обсуждении гомоморфных иерархий классов.
Мудрые курсоры и надежность итераторов
Курсор может использоваться для вставки объекта в некоторую позицию коллекции независимо от того, отражена ли данная позиция во внутренних структурах данных коллекции. Именно этот принцип бал заложен в основу перегрузки оператора = для курсоров. Его можно обобщить на другие операции с курсорами. Ниже перечислены типичные расширенные операции с курсорами, выраженные в виде функций класса курсора:
void InsertBefore(Foo* f); |
// Вставить f перед |
курсором |
void InsertAfter(Foo* f); |
// Вставить f после |
курсора |
void RemoveAt(); |
// Удалить объект в |
текущей позиции курсора |
Сказанное относится к широкому диапазону коллекций, в которых существует четко определенная последовательность элементов. Перечисленные операции также могут обеспечиваться итераторами, которые не возвращают курсор как значение функции Next(), а скрывают текущую позицию в итераторе.
Эти операции усложняют соблюдение единой семантики перебора, а в худшем случае — порождают серьезные недостатки дизайна, которые могут угробить вашу программу. Впрочем, проблемы могут возникнуть и без расширенных операций, если изменения в коллекции могут происходить при наличии активных курсоров и итераторов. Представьте себе, что некий фрагмент программы удаляет объект, на который ссылается текущий активный курсор! Приходится особо заботиться, чтобы это не вызвало катастрофических последствий. Главная проблема — сделать курсор надежным, чтобы они могли пережить обновление своих базовых коллекций.
Для примера возьмем связанный список и его итератор.
A B
Курсоры A и B используются для отслеживания текущей позиции двух разных итераторов в одном списке. Все отлично работает, пока список остается без изменений. Но стоит клиенту одного из итераторов воспользоваться курсором для обновления списка, как немедленно возникают проблемы:
125
•Если клиент выполнит операцию «вставки после» с курсором B, оба итератора при возобновлении перебора увидят только что вставленный объект.
•Если клиент выполнит операцию «вставки до» с курсором B или «вставки после» с курсором A, итератор-владелец A увидит вставленный объект, а итератор-владелец B — нет.
•Если клиент удалит объект в позиции B, A никогда не увидит этого объекта, хотя тот находился на споем месте, когда итератор-владелец A начал перебор списка.
•Если клиент удалит объект в позиции A, B успеет увидеть этот объект перед тем, как произошло удаление.
•При выполнении вставки после любого курсора в некоторых алгоритмах вставки возникает бесконечная рекурсия, поскольку каждый только что вставленный объект может инициировать вставку другого объекта.
•Если A и B ссылаются на общий элемент списка, а один из них этот элемент удалит — «Здравствуй, дебаггер!»
Короче, при внесении изменений в коллекцию во время перебора семантика превращается в сплошной винегрет. А если при этом одновременно работают два и более итератора, результаты можно определять по броскам кубиков.
На самом деле списки — случай относительно простой. Подумайте, что произойдет, если коллекция хранится в виде массива (независимо от того, представляется ли она клиенту массивом или нет), а курсор располагает целочисленным индексом в этом массиве.
A B
Чтобы обеспечить выполнение вставки «до/после» и удаления, приходится сдвигать элементы массива над позицией вставки или удалять одни элемент выше или ниже. Если на диаграмме удалить элемент в A и сдвинуть все, что находится выше, на одну позицию вниз, B пропустит позицию. Если вставить элемент в A, B увидит один и тот же объект дважды.
Семантика перебора должна быть намного более ясной и более предсказуемой. Для большинства приложений порядок элементов следует фиксировать на момент начала перебора, что на него не влияли последующие операции вставки и удаления. Как правило, идиомы итератора и курсора должны соблюдать два правила:
1. Итератор должен перебирать объекты коллекции на момент своего конструирования.
2.Курсор должен оставаться действительным от момента конструирования до момента уничтожения. Другими словами, программа не должна выполнять операции, после которых активный курсор может потерять работоспособность. Это не означает, что значение в позиции курсора должно оставаться одним и тем же — речь идет лишь о том, что курсор обязан сохранять работоспособность.
Эти правила вносят некоторый порядок в то, что грозило превратиться в абсолютный хаос. Первое из них можно назвать «принципом затенения», поскольку все изменения, вносимые в коллекцию после конструирования итератора, скрываются («затеняются») от него. Это одна из глобальных концепций дизайна, по которой запросто можно написать отдельную книгу, но, к счастью, у нас поставлена более приземленная цель — продемонстрировать те идиомы С++, в которых воплощаются практические решения.
126
Частные копии коллекций
Если итератор и его курсор не позволяют вносить изменения в коллекцию, существует простой выход: создать частную копию коллекции в конструкторе итератора. На псевдокоде это выглядит так:
class Iterator { private:
Collection collection;
Cursor location; // Текущая позиция в копии public:
Iterator(Collection& c)
: collection(c), location(collection.First()) {} bool More();
Foo* Next();
};
Конструктор итератора с помощью конструктора копий класса Collection создает вторую частную копию коллекции. Перед вами — один из редких случаев, когда действительно имеет значение тот факт, что переменные класса конструируются в порядке их перечисления; объект collection должен быть сконструирован раньше объекта location, в противном случае вам предстоят мучения с отладкой функции First().
Коллекции объектов или коллекции указателей?
Эта схема обычно используется в ситуациях, когда коллекция состоит из указателей или ссылок на объекты, которые во всем остальном никак не связаны с коллекцией. В других коллекциях вместо указателей или ссылок содержатся собственно объекты.
template <class Type, int Size>
class Array { |
|
|
private: |
|
|
int Size; |
// Количество объектов Type |
|
Type elements[size]; |
// Объекты (внутренние) |
|
// и т.д. |
|
|
}; |
|
|
Здесь объекты буквально внедряются в коллекцию. Чтобы продублировать коллекцию, вам придется скопировать не только указатели, но и объекты — а это может обойтись слишком дорого. С другой стороны, может возникнуть необходимость в том, чтобы итератор возвращал указатель или ссылку на исходный объект исходной коллекции, а не на копию. В любом случае вариант с частными коллекциями отпадает.
Тот же принцип действует каждый раз, когда коллекция представляет собой набор ведущих указателей на ее содержимое. Да, она содержит указатели, а не объекты, однако коллекция имеет право удалять эти объекты, поэтому частная копия будет неустойчивой. Некоторые вопросы управления памятью, связанные с этой проблемой — конкретнее, сборка мусора — рассматриваются в части 4 этой книги.
Упрощение частной коллекции
Предположим, исходная коллекция представляет собой бинарное дерево или другую сложную структуру данных. Так ли необходимо воспроизводить в копии все дополнительные издержки древовидной структуры, если учесть, что вы не собираетесь пользоваться индексированным доступом? Существует общепринятое решение — создать в качестве частной копии упрощенный вариант коллекции. Это будет проще, если в классе коллекции имеется оператор преобразования, порождающий экземпляр упрощенной коллекции. Вместо конструктора копий коллекции итератор использует ее оператор преобразования:
class |
SimpleCollection; |
// Упрощенный вариант |
class |
ComplexCollection |
{ |
127
public:
operator SimpleCollection*();
};
Существует и другой, похожий вариант — создать в классе SimpleCollection конструкторы для всех остальных типов коллекций. Однако с точки зрения дизайна такое решение неудачно — каждый раз, когда вы придумаете какую-нибудь новую экзотическую коллекцию, вам придется изменять класс SimpleCollection. Для таких случаев существуют операторы преобразования.
Если использовать этот вариант, итератор становится универсальным и подходящим для различных типов коллекций. Итератору не нужно ничего знать об исходной коллекции. Конструктору итератора передается адрес упрощенной коллекции вместо исходной, при этом интерфейс выглядит так:
class Iterator { private:
SimpleCollection* collection;
Cursor location; // Текущая позиция в копии public:
Iterator(SimpleCollection* c)
: collection(c), location(collection->First()) {} bool More();
bool Next();
};
Внутренние и внешние итераторы
Вернемся к итераторам, работающим с исходной коллекцией. Существуют два типа итераторов: относящиеся к внутренней реализации коллекции (например, для приведенного выше класса SimpleCollection) и открытые внешнему миру. Они называются внутренними (internal iterator) и внешними (external iterator) итераторами соответственно.
Внутренний итератор обычно представляет собой тупой, ненадежный итератор, который перебирает объекты коллекции в ее текущем состоянии. Если в коллекции происходит вставка или удаление, внутренние итераторы начинают выкидывать все те странные фортели, о которых говорилось в начале раздела. По этой причине их тщательно прячут от шаловливых рук клиента. Как правило, внутренние итераторы тесно связаны со структурами данных, использованными в реализации коллекции. Как и любые другие итераторы, они могут возвращать *-указатель или курсор в зависимости от ваших потребностей.
Внешние итераторы соблюдают принцип затенения. Затенения можно добиться многими способами, часть из которых рассматривается далее в этой главе и в главе 9. Как всегда, суть кроется не в конкретном алгоритме или структуре данных, а в том, как спрятать их от публики.
Временные внутренние итераторы
Если внешний итератор создает частную копию коллекции (см. предыдущий раздел) и при этом не существует оператора преобразования или конструктора, способного превратить исходную коллекцию в частную, в конструкторе внешнего итератора можно воспользоваться внутренним итератором. В следующем фрагменте два внутренних итератора объединяются в реализации одного внешнего:
class ExternalIterator { |
|
private: |
|
SimpleCollection collection; |
|
SimpleIterator* my_iter; |
// Возвращается коллекцией |
public: ExternalIterator(ComplexCollection* c)
{
InternalIterator* iter = c->Iterator();
128
while (c->More())
collection += *(c->Next()); delete iter;
my_iter = collection->Iterator();
}
bool More() { return my_iter->More(); } bool Next() { return my_iter->Next(); }
};
ComplexCollection предоставляет внутренний итератор, который существует ровно столько, сколько необходимо для создания копии. SimpleCollection возвращает итератор, используемый для реализации функции More() и Next() внешнего итератора. Конечно, все могло бы выглядеть намного элегантнее, если бы у SimpleCollection был конструктор с аргументом ComplexCollection или у
ComplexCollection — операторная функция преобразования operator SimpleCollection(). Но даже при их отсутствии класс итератора обеспечивает весь необходимый уровень инкапсуляции.
Устойчивые внутренние итераторы
Термин «устойчивый» (persistent) означает, что внутренний итератор существует до тех пор, пока существует внешний итератор (my_iter в предыдущем примере). Внутренний итератор может быть переменной класса внешнего итератора, как было показано, а при достаточной осторожности его можно создать как производный класс посредством закрытого наследования. Вариант с закрытым наследованием может выглядеть так:
//В файле .h class Collection { public:
class ExternalIterator { public:
virtual bool More() = 0; virtual Foo* Next() = 0;
};
ExternalIterator* Iterator();
};
//В файле .cpp
//Настоящий класс, возвращаемый клиентам class RealExternalIterator
:public ExternalIterator, private InternalIterator
(...);
Collection:ExternalIterator* Collection::Iterator()
{
return new RealExternalIterator(this);
}
Обладающий локальной областью действия ExternalIterator обеспечивает абстрактный интерфейс, предоставляемый клиенту. Настоящий возвращаемый класс, RealExternalIterator, порожден от Collection::ExternalIterator посредством открытого наследования, а также (о чем клиент не подозревает) — от SimpleIterator посредством закрытого наследования. Как и в большинстве проблем дизайна С++, закрытое наследование проще реализуется, а делегирование переменной класса оказывается более универсальным. Например, вы можете на полпути заменить переменную, чтобы сцепить несколько внутренних итераторов в одном внешнем.
- #08.05.20136.97 Mб16W.H.Press, S.A.Teukolsky, W.T.Vetterling, B.P.Flannery - FORTRAN NUMERICAL RECIPES (Fortran 77) Vol.1.djvu
- #08.05.20133.43 Mб19W.H.Press, S.A.Teukolsky, W.T.Vetterling, B.P.Flannery - FORTRAN NUMERICAL RECIPES (Fortran 90) Vol.2.djvu
- #08.05.201310.54 Mб21W.H.Press, S.A.Teukolsky, W.T.Vetterling, B.P.Flannery - NUMERICAL RECIPES IN C.djvu
- #
- #
- #
- #
- #