straustrup2 (852740), страница 55
Текст из файла (страница 55)
Сперва в описанияхклассов будет приведена только общая часть, а реализация будет дана в следующем разделе. Этоделается за тем, чтобы вопросы проектирования классов не затемнялись деталями их реализации.Начнем с типа 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;}Но поскольку структура slink не может содержать никакой информации помимо связи, этот пример неслишком интересен. Чтобы воспользоваться 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();207Бьерн Страуструп.Язык программирования С++// ...delete p;}Здесь все нормально, но поскольку определение класса slist_base дано через структуру slink,приходится использовать явное приведение типа для преобразования значения типа slink*,возвращаемого функцией slist_base::get(), в name*.
Это некрасиво. Для большой программы, в котороймного списков и производных от slink классов, это к тому же чревато ошибками. Нам пригодилась бынадежная по типу версия класса slist_base:template<class T>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) обозначает односвязный список с принудительной связью. Этотшаблон типа можно использовать так:void f(const char* s){Islist<name> ilst;ilst.insert(new name(s));// ...name* p = ilst.get();// ...delete p}Попытки некорректного использования будет выявлены на стадии трансляции:class expr : public slink {// ...};void g(expr* e){Islist<name> ilst;ilst.insert(e);// ошибка: Islist<name>::insert(),// а нужно name*// ...}Нужно отметить несколько важных моментов относительно нашего примера. Во-первых, решениенадежно в смысле типов (преграда тривиальным ошибкам ставится в очень ограниченной частипрограммы, а именно, в функциях доступа из Islist). Во-вторых, надежность типов достигается безувеличения затрат времени и памяти, поскольку функции доступа из Islist тривиальны и реализуютсяподстановкой.
В-третьих, поскольку вся настоящая работа со списком делается в реализации классаslist_base (пока еще не представленной), никакого дублирования функций не происходит, а исходныйтекст реализации, т.е. функции slist_base, вообще не должен быть доступен пользователю. Это можетбыть существенно в коммерческом использовании служебных программ для списков.
Кроме того,достигается разделение между интерфейсом и его реализацией, и становится возможной сменареализации без перетрансляции программ пользователя. Наконец, простой список с принудительнойсвязью близок по использованию памяти и времени к оптимальному решению. Иными словами, такойподход близок к оптимальному по времени, памяти, упрятыванию данных и контролю типов и в тоже208Бьерн Страуструп.Язык программирования С++время он обеспечивает большую гибкость и компактность выражений.К сожалению, объект может попасть в Islist только, если он является производным от slink. Значитнельзя иметь список Islist из значений типа int, нельзя составить список из значений какого-то ранееопределенного типа, не являющегося производным от slink.
Кроме того, придется постараться, чтобывключить объект в два списка Islist ($$6.5.1).8.3.2 Список без принудительной связиПосле "экскурса" в вопросы построения и использования списка с принудительной связью перейдем кпостроению списков без принудительной связи.
Это значит, что элементы списка не обязаны содержатьдополнительную информацию, помогающую в реализации списочного класса. Поскольку мы больше неможем рассчитывать, что объект в списке имеет поле связи, такую связь надо предусмотреть вреализации: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);209Бьерн Страуструп.Язык программирования С++lst2.insert(i);// ...int i1 = lst1.get();int i2 = lst2.get();// ...}Однако, список с принудительной связью, например Islist, позволял создавать существенно болееэффективную программу и давал более компактное представление.
Действительно, при каждомвключении объекта в список Slist нужно разместить объект Tlink, а при каждом удалении объекта из Slistнужно удалить объект Tlink, причем каждый раз копируется объект типа T. Когда возникает такаяпроблема дополнительных расходов, могут помочь два приема.
Во-первых, Tlink является прямымкандидатом для размещения с помощью практически оптимальной функции размещения специальногоназначения (см. $$5.5.6). Тогда дополнительные расходы при выполнении программы сократятся дообычно приемлемого уровня. Во-вторых, полезным оказывается такой прием, когда объекты хранятся в"первичном" списке, имеющим принудительную связь, а списки без принудительной связи используютсятолько, когда требуется включение объекта в несколько списков:void f(name* p){Islist<name> lst1;Slist<name*> lst2;lst1.insert(p);lst2.insert(p);////////связь через объект `*p'для хранения `p' используетсяотдельный объект типа список...}Конечно, подобные трюки можно делать только в отдельном компоненте программы, чтобы недопустить путаницы списочных типов в интерфейсах различных компонент.
Но это именно тот случай,когда ради эффективности и компактности программы на них стоит идти.Поскольку конструктор Slist копирует параметр для insert(), список Slist пригоден только для такихнебольших объектов, как целые, комплексные числа или указатели. Если для объектов копированиеслишком накладно или неприемлемо по смысловым причинам, обычно выход бывает в том, чтобывместо объектов помещать в список указатели на них. Это сделано в приведенной выше функции f()для lst2.Отметим, что раз параметр для Slist::insert() копируется, передача объекта производного классафункции insert(), ожидающей объект базового класса, не пройдет гладко, как можно было (по наивности)подумать:class smiley : public circle {/* ...
*/ };void g1(Slist<circle>& olist, const smiley& grin){olist.insert(grin);// ловушка!}В список будет включена только часть circle объекта типа smiley. Отметим, что эта неприятность будетобнаружена транслятором в том случае, который можно считать наиболее вероятным. Так, если бырассматриваемый базовый класс был абстрактным, транслятор запретил бы "урезание" объектапроизводного класса:void g2(Slist<shape>& olist, const circle& c){olist.insert(c);// ошибка: попытка создать объект// абстрактного класса}Чтобы избежать "урезания" объекта нужно использовать указатели:void g3(Slist<shape*>& plist, const smiley& grin){210Бьерн Страуструп.Язык программирования С++// прекрасноolist.insert(&grin);}Не нужно использовать параметр-ссылку для шаблонного класса:void g4(Slist<shape&>& rlist, const smiley& grin){rlist.insert(grin);// ошибка: будет созданы команды,// содержащие ссылку на ссылку (shape&&)}При генерации по шаблону типа ссылки, используемые подобным образом, приведут ошибкам в типах.Генерация по шаблону типа для функцииSlist::insert(T&);приведет к появлению недопустимой функцииSlist::insert(shape&&);Ссылка не является объектом, поэтому нельзя иметь ссылку на ссылку.Поскольку список указателей является полезной конструкцией, имеет смысл дать ему специальное имя:template<class T>class Splist : privatepublic:void insert(T* p)void append(T* p)T* get() { return};Slist<void*> {{ Slist<void*>::insert(p); }{ Slist<void*>::append(p); }(T*) Slist<void*>::get(); }class Isplist : private slist_base {public:void insert(T* p) { slist_base::insert(p); }void append(T* p) { slist_base::append(p); }T* get() { return (T*) slist_base::get(); }};Эти определения к тому же улучшают контроль типов и еще больше сокращают необходимостьдублировать функции.Часто бывает полезно, чтобы тип элемента, указываемый в шаблоне типа, сам был шаблоннымклассом.
Например, разреженную матрицу, содержащую даты, можно определить так:typedef Slist< Slist<date> > dates;Обратите внимание на наличие пробелов в этом определении. Если между первой и второй угловойскобкой > нет пробелов, возникнет синтаксическая ошибка, поскольку >> в определенииtypedef Slist<Slist<date>> dates;будет трактоваться как операция сдвига вправо. Как обычно, вводимое в typedef имя служит синонимомобозначаемого им типа, а не является новым типом. Конструкция typedef полезна для именования длядлинных имен шаблонных классов также, как она полезна для любых других длинных имен типов.Отметим, что параметр шаблона типа, который может по разному использоваться в его определении,должен все равно указываться среди списка параметров шаблона один раз.
Поэтому шаблон типа, вкотором используется объект T и список элементов T, надо определять так:template<class T> class mytemplate {T ob;Slist<T> slst;// ...};а вовсе не так:211Бьерн Страуструп.Язык программирования С++template<class T, class Slist<t> > class mytemplate {T obj;Slist<T> slst;// ...};В $$8.6 и $$R.14.2 даны правила, что может быть параметром шаблона типа.8.3.3 Реализация спискаРеализация функций slist_base очевидна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
