straustrup2 (852740), страница 56
Текст из файла (страница 56)
Единственная трудность связана с обработкой ошибок.Например, что делать если пользователь с помощью функции 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().
Каждый из вариантов впоследующих разделах будет иллюстрировать общий метод.Как обычно мы сосредоточимся на организации программы, а не на разработке ее алгоритма, поэтомуиспользоваться будет тривиальный алгоритм. Все варианты шаблона типа для sort() нужны для того,чтобы показать возможности языка м полезные приемы программирования. Варианты не упорядоченыв соответствии с тем, насколько они хороши. Кроме того, можно обсудить и традиционные варианты безшаблонов типа, в частности, передачу указателя на функцию, производящую сравнение.215Бьерн Страуструп.Язык программирования С++8.4.1 Простой шаблон типа для глобальной функцииНачнем с простейшего шаблона для sort():template<class T> void sort(Vector<T>&);void f(Vector<int>& vi,Vector<String>& vc,Vector<int>& vi2,Vector<char*>& vs){sort(vi);// sort(Vector<int>& v);sort(vc);// sort(Vector<String>& v);sort(vi2);// sort(Vector<int>& v);sort(vs);// sort(Vector<char*>& v);}Какая именно функция sort() будет вызываться определяется фактическим параметром.
Программистдает определение шаблона типа для функции, а задача системы программирования обеспечитьсоздание правильных вариантов функции по шаблону и вызов соответствующего варианта. Например,простой шаблон с алгоритмом пузырьковой сортировки можно определить так:template<class T> void sort(Vector<T>& v)/*Сортировка элементов в порядке возрастанияИспользуется сортировка по методу пузырька*/{unsigned n = v.size();for (int i=0; i<n-1; i++)for (int j=n-1; i<j; j--)if (v[j] < v[j-1]) { // меняем местами v[j] и v[j-1]T temp = v[j];v[j] = v[j-1];v[j-1] = temp;}}Советуем сравнить это определение с функцией сортировки с тем же алгоритмом из $$4.6.9.Существенное отличие этого варианта в том, что вся необходимая информация передается вединственном параметре v.
Поскольку тип сортируемых элементов известен (из типа фактическогопараметра, можно непосредственно сравнивать элементы, а не передавать указатель на производящуюсравнение функцию. Кроме того, нет нужды возиться с операцией sizeof. Такое решение кажется болеекрасивым и к тому же оно более эффективно, чем обычное. Все же оно сталкивается с трудностью. Длянекоторых типов операция < не определена, а для других, например char*, ее определениепротиворечит тому, что требуется в приведенном определении шаблонной функции.
(Действительно,нам нужно сравнивать не указатели на строки, а сами строки). В первом случае попытка создатьвариант sort() для таких типов закончится неудачей (на что и следует надеяться) , а во второмпоявиться функция, производящая неожиданный результат.Чтобы правильно сортировать вектор из элементов char* мы можем просто задать самостоятельноподходящее определение функцииsort(Vector<char*>&):void sort(Vector<char*>& v){unsigned n = v.size();for (int i=0; i<n-1; i++)for ( int j=n-1; i<j; j--)if (strcmp(v[j],v[j-1])<0) {// меняем местами v[j] и v[j-1]char* temp = v[j];v[j] = v[j-1];216Бьерн Страуструп.Язык программирования С++v[j-1] = temp;}}Поскольку для векторов из указателей на строки пользователь дал свое особое определение функцииsort(), оно и будет использоваться, а создавать для нее определение по шаблону с параметром типаVector<char*>& не нужно. Возможность дать для особо важных или "необычных" типов своеопределение шаблонной функции дает ценное качество гибкости в программировании и может бытьважным средством доведения программы до оптимальных характеристик.8.4.2 Производные классы позволяют ввести новые операцииВ предыдущем разделе функция сравнения была "встроенной" в теле sort() (просто использоваласьоперация <).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
