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;

else

last = a;

last->next = a;

}

Заметьте, что last->next - первый элемент списка.

void slist_base::append(slink* a) // добавить в конец списка

{

if (last) {

a->next = last->next;

last = last->next = a;

}

else

last = a->next = a;

}

slist* slist_base::get() // удалить и возвратить начало списка

{

if (last == 0)

slist_handler("нельзя взять из пустого списка");

slink* f = last->next;

if (f== last)

last = 0;

else

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 {

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(). В обоих вариантах предполагается взаимосвязь

между контейнерным классом и итератором для него, так что можно

при выполнении итератора обработать случаи, когда элементы добавляются

или удаляются из контейнера. Этот и некоторые другие способы задания

итераторов были бы невозможны, если бы итератор зависел от функции

пользователя, в которой есть указатели на элементы из контейнера.

Как правило, контейнер или его итераторы реализуют понятие "установить

итерацию на начало" и понятие "текущего элемента".

Если понятие текущего элемента предоставляет не итератор, а сам

контейнер, итерация происходит в принудительном порядке по отношению

к контейнеру аналогично тому, как поля связи принудительно хранятся

в объектах из контейнера. Значит трудно одновременно вести две

итерации для одного контейнера, но расходы на память и время при такой

организации итерации близки к оптимальным. Приведем пример:

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.