Бьерн Страуструп. Язык программирования С++
жүктеу/скачать 3.27 Mb.
|
- Бұл бет үшін навигация:
- 8.3.4 Итерация
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; };
указатель на последний элемент замкнутого списка:
{ if (last) a->next = last->next; else
last = a; last->next = a; }
{ if (last) { a->next = last->next; last = last->next = a; } else
last = a->next = a; }
{ if (last == 0) slist_handler("нельзя взять из пустого списка"); slink* f = last->next; if (f== last) last = 0; else last->next = f->next; return f; }
функцию, а не сама функция. Тогда вызов
завести функцию, которая поможет пользователю создавать свои обработчики ошибок:
{ PFV old = slist_handler; slist_handler = a; return old; }
альтернативный способ обработки ошибок, но и способ реализации slist_handler.
В классе 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()() };
{ cs = &s; ce = cs->last; }
// возвращает 0, когда итерация кончается { slink* ret = ce ? (ce=ce->next) : 0; if (ce == cs->last) ce = 0; return ret; }
Islist. Сначала надо определить дружественные классы для итераторов по соответствующим контейнерным классам:
friend class Islist_iter // ... };
template friend class Slist_iter // ... };
их шаблонного класса. Это способ определения в условиях взаимной зависимости шаблонов типа. Теперь можно определить сами итераторы:
class Islist_iter : private slist_base_iter { public: Islist_iter(Islist T* operator()() { return (T*) slist_base_iter::operator()(); } };
class Slist_iter : private slist_base_iter { public: Slist_iter(Slist inline T* operator()(); };
{ return ((Tlink } Заметьте, что мы опять использовали прием, когда из одного базового класса строится семейство производных классов (а именно, шаблонный класс). Мы используем наследование, чтобы выразить общность классов и избежать ненужного дублирования функций. Трудно переоценить стремление избежать дублирования функций при реализации таких простых и часто используемых классов как списки и итераторы. Пользоваться этими итераторами можно так:
{ Islist Slist lst1.insert(p); lst2.insert(p); // ...
const name* p; while (p=iter1()) { list_iter 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 // медленный поиск имен-дубликатов { list_iter 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. жүктеу/скачать 3.27 Mb. Достарыңызбен бөлісу:
|