Бьерн Страуструп. Язык программирования С++
жүктеу/скачать 3.27 Mb.
|
- Бұл бет үшін навигация:
- 8.3.1 Список с принудительной связью
8.3 Шаблоны типа для спискаНа практике при разработке класса, служащего коллекцией объектов, часто приходится учитывать взаимоотношения использующихся в реализации классов, управление памятью и необходимость определить итератор по содержимому коллекции. Часто бывает так, что несколько родственных классов разрабатываются совместно ($$12.2). В качестве примера мы предложим семейство классов, представляющих односвязные списки и шаблоны типа для них. 8.3.1 Список с принудительной связьюВначале определим простой список, в котором предполагается, что в каждом заносимом в список объекте есть поле связи. Потом этот список будет использоваться как строительный материал для создания более общих списков, в которых объект не обязан иметь поле связи. Сперва в описаниях классов будет приведена только общая часть, а реализация будет дана в следующем разделе. Это делается за тем, чтобы вопросы проектирования классов не затемнялись деталями их реализации. Начнем с типа slink, определяющего поле связи в односвязном списке: struct slink { slink* next; slink() { next = 0; } slink(slink* p) { next = p; } };
любого, производного от slink, класса: class slist_base { // ...
public: int insert(slink*); // добавить в начало списка int append(slink*); // добавить к концу списка slink* get(); // удалить и возвратить начало списка // ... };
его можно использовать только в том случае, когда все элементы имеют поле slink, которое используется как указатель на slist_base. Само имя slist_base (базовый односвязный список) говорит, что этот класс будет использоваться как базовый для односвязных списочных классов. Как обычно, при разработке семейства родственных классов возникает вопрос, как выбирать имена для различных членов семейства. Поскольку имена классов не могут перегружаться, как это делается для имен функций, для обуздания размножения имен перегрузка нам не поможет. Класс slist_base можно использовать так: void f() { slist_base slb; slb.insert(new slink); // ...
slink* p = slb.get(); // ...
delete p; }
помимо связи, этот пример не слишком интересен. Чтобы воспользоваться slist_base, надо определить полезный, производный от slink, класс. Например, в трансляторе используются узлы дерева программы name (имя), которые приходится связывать в список: class name : public slink { // ...
}; void f(const char* s) { slist_base slb; slb.insert(new name(s)); // ...
name* p = (name*)slb.get(); // ...
delete p; }
дано через структуру slink, приходится использовать явное приведение типа для преобразования значения типа slink*, возвращаемого функцией slist_base::get(), в name*. Это некрасиво. Для большой программы, в которой много списков и производных от slink классов, это к тому же чревато ошибками. Нам пригодилась бы надежная по типу версия класса slist_base: template class Islist : private slist_base { public: void insert(T* a) { slist_base::insert(a); } T* get() { return (T*) slist_base::get(); } // ...
}; Приведение в функции Islist::get() совершенно оправдано и надежно, поскольку в классе Islist гарантируется, что каждый объект в списке действительно имеет тип T или тип производного от T класса. Отметим, что slist_base является частным базовым классом Islist. Мы нет хотим, чтобы пользователь случайно натолкнулся на ненадежные детали реализации. Имя Islist (intrusive singly linked list) обозначает односвязный список с принудительной связью. Этот шаблон типа можно использовать так:
{ Islist ilst.insert(new name(s)); // ...
name* p = ilst.get(); // ...
delete p }
трансляции:
// ...
}; void g(expr* e) { Islist ilst.insert(e); // ошибка: Islist // а нужно name* // ... }
Во-первых, решение надежно в смысле типов (преграда тривиальным ошибкам ставится в очень ограниченной части программы, а именно, в функциях доступа из Islist). Во-вторых, надежность типов достигается без увеличения затрат времени и памяти, поскольку функции доступа из Islist тривиальны и реализуются подстановкой. В-третьих, поскольку вся настоящая работа со списком делается в реализации класса slist_base (пока еще не представленной), никакого дублирования функций не происходит, а исходный текст реализации, т.е. функции slist_base, вообще не должен быть доступен пользователю. Это может быть существенно в коммерческом использовании служебных программ для списков. Кроме того, достигается разделение между интерфейсом и его реализацией, и становится возможной смена реализации без перетрансляции программ пользователя. Наконец, простой список с принудительной связью близок по использованию памяти и времени к оптимальному решению. Иными словами, такой подход близок к оптимальному по времени, памяти, упрятыванию данных и контролю типов и в тоже время он обеспечивает большую гибкость и компактность выражений. К сожалению, объект может попасть в Islist только, если он является производным от slink. Значит нельзя иметь список Islist из значений типа int, нельзя составить список из значений какого-то ранее определенного типа, не являющегося производным от slink. Кроме того, придется постараться, чтобы включить объект в два списка Islist ($$6.5.1). жүктеу/скачать 3.27 Mb. Достарыңызбен бөлісу:
|