|
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 Array {
private:
int
Size;
//
Количество объектов Type
Type
elements[size];
//
Объекты (внутренние)
// и т.д.
};
Здесь объекты буквально внедряются в коллекцию. Чтобы продублировать коллекцию, вам придется
скопировать не только указатели, но и объекты — а это может обойтись слишком дорого. С другой
стороны, может возникнуть необходимость в том, чтобы итератор возвращал указатель или ссылку на
исходный объект исходной коллекции, а не на копию. В любом случае вариант с частными
коллекциями отпадает.
Тот же принцип действует каждый раз, когда коллекция представляет собой набор ведущих указателей
на ее содержимое. Да, она содержит указатели, а не объекты, однако коллекция имеет право удалять
эти объекты, поэтому частная копия будет неустойчивой. Некоторые вопросы управления памятью,
связанные с этой проблемой — конкретнее, сборка мусора — рассматриваются в части 4 этой книги.
Упрощение частной коллекции
Предположим, исходная коллекция представляет собой бинарное дерево или другую сложную
структуру данных. Так ли необходимо воспроизводить в копии все дополнительные издержки
древовидной структуры, если учесть, что вы не собираетесь пользоваться индексированным доступом?
Существует общепринятое решение — создать в качестве частной копии упрощенный вариант
коллекции. Это будет проще, если в классе коллекции имеется оператор преобразования,
порождающий экземпляр упрощенной коллекции. Вместо конструктора копий коллекции итератор
использует ее оператор преобразования:
class SimpleCollection; //
Упрощенный вариант
class ComplexCollection {
Do'stlaringiz bilan baham: |
