Бьерн Страуструп - Язык программирования С++. Главы 5-8
Страница 76. Итерация
|
|
Страница 76 из 88
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.
|