Б. Страуструп - Язык программирования С++ (1119446), страница 58
Текст из файла (страница 58)
Это сделано в приведенной выше функции 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 очевидна. Единственная трудность связана с обработкой ошибок.Например, что делать если пользователь с помощью функции get() пытается взять элемент из пустогосписка.
Подобные ситуации разбираются в функции обработки ошибок slist_handler(). Более развитыйметод, рассчитанный на особые ситуации, будет обсуждаться в главе 9.Приведем полное описание класса slist_base:class slist_base {slink* last; // last->next является началом спискаpublic:void insert(slink* a);// добавить в начало спискаvoid append(slink* a);// добавить в конец спискаslink* get();// удалить и возвратить// начало спискаvoid clear() { last = 0; }slist_base() { last = 0; }slist_base(slink* a) { last = a->next = a; }friend class slist_base_iter;};Чтобы упростить реализацию обеих функций insert и append, хранится указатель на последний элементзамкнутого списка:void slist_base_insert(slink* a){if (last)a->next = last->next;elselast = a;last->next = a;}// добавить в начало спискаЗаметьте, что last->next - первый элемент списка.void slist_base::append(slink* a) // добавить в конец списка{if (last) {a->next = last->next;last = last->next = a;}elselast = a->next = a;}slist* slist_base::get() // удалить и возвратить начало списка{if (last == 0)slist_handler("нельзя взять из пустого списка");slink* f = last->next;if (f== last)last = 0;else212Бьерн Страуструп.Язык программирования С++last->next = f->next;return f;}Возможно более гибкое решение, когда slist_handler - указатель на функцию, а не сама функция.
Тогдавызовslist_handler("нельзя взять из пустого списка");будет задаваться так(*slist_handler)(" нельзя взять из пустого списка");Как мы уже делали для функции new_handler ($$3.2.6), полезно завести функцию, которая поможетпользователю создавать свои обработчики ошибок:typedef void (*PFV)(const char*);PFV set_slist_handler(PFV a){PFV old = slist_handler;slist_handler = a;return old;}PFV slist_handler = &default_slist_handler;Особые ситуации, которые обсуждаются в главе 9, не только дают альтернативный способ обработкиошибок, но и способ реализации slist_handler.8.3.4 ИтерацияВ классе slist_base нет функций для просмотра списка, можно только вставлять и удалять элементы.Однако, в нем описывается как друг класс slist_base_iter, поэтому можно определить подходящий длясписка итератор.
Вот один из возможных, заданный в том стиле, какой был показан в $$7.8:class slist_base_iter {slink* ce;// текущий элементslist_base* cs;// текущий списокpublic:inline slist_base_iter(slist_base& s);inline slink* operator()()};slist_base_iter::slist_base_iter(slist_base& s){cs = &s;ce = cs->last;}slink* slist_base_iter::operator()()// возвращает 0, когда итерация кончается{slink* ret = ce ? (ce=ce->next) : 0;if (ce == cs->last) ce = 0;return ret;}Исходя из этих определений, легко получить итераторы для Slist и Islist. Сначала надо определитьдружественные классы для итераторов по соответствующим контейнерным классам:template<class T> class Islist_iter;template<class T> class Islist {213Бьерн Страуструп.Язык программирования С++friend class Islist_iter<T>;// ...};template<class T> class Slist_iter;template<class T> class Slist {friend class Slist_iter<T>;// ...};Обратите внимание, что имена итераторов появляются без определения их шаблонного класса.
Этоспособ определения в условиях взаимной зависимости шаблонов типа.Теперь можно определить сами итераторы:template<class T>class Islist_iter : private slist_base_iter {public:Islist_iter(Islist<T>& s) : slist_base_iter(s) { }T* operator()(){ return (T*) slist_base_iter::operator()(); }};template<class T>class Slist_iter : private slist_base_iter {public:Slist_iter(Slist<T>& s) : slist_base_iter(s) { }inline T* operator()();};T* Slist_iter::operator()(){return ((Tlink<T>*) slist_base_iter::operator()())->info;}Заметьте, что мы опять использовали прием, когда из одного базового класса строится семействопроизводных классов (а именно, шаблонный класс). Мы используем наследование, чтобы выразитьобщность классов и избежать ненужного дублирования функций.
Трудно переоценить стремлениеизбежать дублирования функций при реализации таких простых и часто используемых классов каксписки и итераторы. Пользоваться этими итераторами можно так:void f(name* p){Islist<name> lst1;Slist<name> lst2;lst1.insert(p);lst2.insert(p);// ...Islist_iter<name> iter1(lst1);const name* p;while (p=iter1()) {list_iter<name> iter2(lst1);const name* q;while (q=iter2()) {if (p == q) cout << "найден" << *p << '\n';}}}Есть несколько способов задать итератор для контейнерного класса. Разработчик программы илибиблиотеки должен выбрать один из них и придерживаться его.
Приведенный способ может показатьсяслишком хитрым. В более простом варианте можно было просто переименовать operator()() как next(). Вобоих вариантах предполагается взаимосвязь между контейнерным классом и итератором для него, так214Бьерн Страуструп.Язык программирования С++что можно при выполнении итератора обработать случаи, когда элементы добавляются или удаляютсяиз контейнера. Этот и некоторые другие способы задания итераторов были бы невозможны, если быитератор зависел от функции пользователя, в которой есть указатели на элементы из контейнера.
Какправило, контейнер или его итераторы реализуют понятие "установить итерацию на начало" и понятие"текущего элемента".Если понятие текущего элемента предоставляет не итератор, а сам контейнер, итерация происходит впринудительном порядке по отношению к контейнеру аналогично тому, как поля связи принудительнохранятся в объектах из контейнера. Значит трудно одновременно вести две итерации для одногоконтейнера, но расходы на память и время при такой организации итерации близки к оптимальным.Приведем пример:class slist_base {// ...slink* last; // last->next голова спискаslink* current; // текущий элементpublic:// ...slink* head() { return last?last->next:0; }slink* current() { return current; }void set_current(slink* p) { current = p; }slink* first() { set_current(head()); return current; }slink* next();slink* prev();};Подобно тому, как в целях эффективности и компактности программы можно использовать для одногообъекта как список с принудительной связью, так и список без нее, для одного контейнера можноиспользовать принудительную и непринудительную итерацию:void f(Islist<name>& ilst)// медленный поиск имен-дубликатов{list_iter<name> slow(ilst); // используется итераторname* p;while (p = slow()) {ilst.set_current(p); // рассчитываем на текущий элементname* q;while (q = ilst.next())if (strcmp(p->string,q->string) == 0)cout << "дубликат" << p << '\n';}}Еще один вид итераторов показан в $$8.8.8.4 Шаблоны типа для функцийИспользование шаблонных классов означает наличие шаблонных функций-членов.
Помимо этого,можно определить глобальные шаблонные функции, т.е. шаблоны типа для функций, не являющихсячленами класса. Шаблон типа для функций порождает семейство функций точно также, как шаблонтипа для класса порождает семейство классов. Эту возможность мы обсудим на последовательностипримеров, в которых приводятся варианты функции сортировки sort(). Каждый из вариантов впоследующих разделах будет иллюстрировать общий метод.Как обычно мы сосредоточимся на организации программы, а не на разработке ее алгоритма, поэтомуиспользоваться будет тривиальный алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
