Язык программирования C++ для профессионалов
Список без принудительной связи
После "экскурса" в вопросы построения и использования списка с принудительной связью перейдем к построению списков без принудительной связи. Это значит, что элементы списка не обязаны содержать дополнительную информацию, помогающую в реализации списочного класса. Поскольку мы больше не можем рассчитывать, что объект в списке имеет поле связи, такую связь надо предусмотреть в реализации:
template<class T> struct Tlink : public slink { T info; Tlink(const T& a) : info(a) { } };
Класс Tlink<T> хранит копию объектов типа T помимо поля связи, которое идет от его базового класса slink. Отметим, что используется инициализатор в виде info(a), а не присваивание info=a. Это существенно для эффективности операции в случае типов, имеющих нетривиальные конструкторы копирования и операции присваивания (§7.11). Для таких типов (например, для String) определив конструктор как
Tlink(const T& a) { info = a; }
мы получим, что будет строиться стандартный объект String, а уже затем ему будет присваиваться значение.
Имея класс, определяющий связь, и класс Islist, получить определение списка без принудительной связи совсем просто:
template<class T> class Slist : private slist_base { public: void insert(const T& a) { slist_base::insert(new Tlink<T>(a)); } void append(const T& a) { slist_base::append(new Tlink<T>(a)); } T get(); // ... };
template<class T> T Slist<T>::get() { Tlink<T>* lnk = (Tlink<T>*) slist_base::get(); T i = lnk->info; delete lnk; return i; }
Работать со списком Slist так же просто, как и со списком Ilist. Различие в том, что можно включать в Slist объект, класс которого не является производным от slink, а также можно включать один объект в два списка:
void f(int i) { Slist<int> lst1; Slist<int> lst2;
lst1.insert(i); lst2.insert(i); // ...
int i1 = lst1.get(); int i2 = lst2.get(); // ... }
Однако, список с принудительной связью, например Islist, позволял создавать существенно более эффективную программу и давал более компактное представление. Действительно, при каждом включении объекта в список Slist нужно разместить объект Tlink, а при каждом удалении объекта из Slist нужно удалить объект Tlink, причем каждый раз копируется объект типа T. Когда возникает такая проблема дополнительных расходов, могут помочь два приема. Во-первых, Tlink является прямым кандидатом для размещения с помощью практически оптимальной функции размещения специального назначения (см. §5.5.6). Тогда дополнительные расходы при выполнении программы сократятся до обычно приемлемого уровня. Во-вторых, полезным оказывается такой прием, когда объекты хранятся в "первичном" списке, имеющим принудительную связь, а списки без принудительной связи используются только, когда требуется включение объекта в несколько списков:
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий