Программирование. Принципы и практика использования C++ Исправленное издание

Мы настоятельно рекомендуем вам, размышляя о списках, рисовать диаграммы, иллюстрирующие операции, которые вы рассматриваете. Манипуляции связанным списком — это тема, в которой один рисунок может заменить тысячу слов.

20.4.1. Операции над списками

Какие операции необходимы для списка?

• Операции, эквивалентные операциям над векторами (создание, определение размера и т.д.), за исключением индексирования.

• Вставка (добавление элемента) и стирание (удаление элемента).

• Нечто, что можно использовать для ссылки на элементы и перемещения по списку: итератор.

В библиотеке STL тип итератора является членом своего класса, поэтому и мы поступим так же.

 template<class Elem> class list {
 // детали представления и реализации
 public:
  class iterator; // тип — член класса :iterator
  iterator begin; // итератор, ссылающийся на первый элемент
  iterator end; // итератор, ссылающийся на последний элемент

  iterator insert(iterator p, const Elem& v); // вставка v

// в список после элемента,

// на который установлен итератор p

  iterator erase(iterator p); // удаление из списка элемента,

// на который установлен итератор p

  void push_back(const Elem& v); // вставка v в конец списка
  void push_front(const Elem& v); // вставка v в начало списка
  void pop_front; // удаление первого элемента
  void pop_back; // удаление последнего элемента

  Elem& front; // первый элемент
  Elem& back; // последний элемент
  // ...
 }

Так же как наш класс vector не совпадал с полной версией стандартного вектора, так и класс list — это далеко не полное определение стандартного списка. В этом определении все правильно; просто оно неполное. Цель “нашего” класса list — объяснить устройство связанных списков, продемонстрировать их реализацию и показать способы использования их основных возможностей. Более подробная информация приведена в приложении Б и в книгах о языке С++, предназначенных для экспертов.

Итератор играет главную роль в определении класса list в библиотеке STL. Итераторы используются для идентификации места вставки или удаления элементов. Кроме того, их используют для “навигации” по списку вместо оператора индексирования. Такое применение итераторов очень похоже на использование указателей при перемещении по массивам и векторам, описанном в разделах 20.1 и 20.3.1. Этот вид итераторов является основным в стандартных алгоритмах (разделы 21.1–21.3).

Почему в классе list не используется индексирование? Мы могли бы проиндексировать узлы, но эта операция удивительно медленная: для того чтобы достичь элемента lst[1000], нам пришлось бы начинать с первого элемента и пройти все элементы по очереди, пока мы не достигли бы элемента с номером 1000. Если вы хотите этого, то можете реализовать эту операцию сами (или применить алгоритм advance; см. раздел 20.6.2). По этой причине стандартный класс list не содержит операции индексирования.

Мы сделали тип итератора для списка членом класса (вложенным классом), потому что нет никаких причин делать его глобальным. Он используется только в списках. Кроме того, это позволяет нам называть каждый тип в контейнере именем iterator. В стандартной библиотеке есть list<T>::iterator, vector<T>::iterator, map<K,V>::iterator и т.д.

20.4.2. Итерация

Итератор списка должен обеспечивать выполнение операций *, ++, == и !=. Поскольку стандартный список является двухсвязным, в нем также есть операция –– для перемещения назад, к началу списка.

 template<class Elem> class list<Elem>::iterator {
  Link<Elem>* curr; // текущий узел
 public:
  iterator(Link* p):curr(p) { }

  // вперед
  iterator& operator++ {curr = curr–>succ; return *this; }

  // назад
  iterator& operator–– { curr = curr–>prev; return *this; }

  // (разыменовать)
  Elem& operator* { return curr–>val; } // получить значение
  bool operator==(const iterator& b) const
  { return curr==b.curr; }
  bool operator!= (const iterator& b) const
  { return curr!=b.curr; }
 };

Эти функции короткие, простые и эффективные: в них нет циклов, нет сложных выражений и подозрительных вызовов функций. Если эта реализация вам не понятна, то посмотрите на диаграммы, приведенные ранее. Этот итератор списка просто представляет собой указатель на узел с требуемыми операциями. Несмотря на то что реализация (код) для класса list<Elem>::iterator сильно отличается от обычного указателя, который использовался в качестве итератора для векторов и массивов, их семантика одинакова. По существу, итератор списка обеспечивает удобные операции ++, ––, *, ==, and != для указателя на узел.

Посмотрим на функцию high еще раз.

 template<class Iterator >
 Iterator high(Iterator first, Iterator last)
 // возвращает итератор на максимальный элемент в диапазоне
 // [first,last)
 {
  Iterator high = first;
  for (Iterator p = first; p!=last; ++p)
  if (*high<*p) high = p;
  return high;