Бьерн Страуструп - Язык программирования С++. Главы 8-10 - Итерация

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.