Программирование

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

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

20.4.2. Итерация

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

template class list::iterator {

  Link* 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::iterator сильно отличается от обычного указателя, который использовался в качестве итератора для векторов и массивов, их семантика одинакова. По существу, итератор списка обеспечивает удобные операции ++, ––, *, ==, and != для указателя на узел.

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

template

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;

}

Мы можем применить ее к объекту класса list.

void f()

{

  list lst;

  int x;

  while (cin >> x) lst.push_front(x);

  list::iterator p = high(lst.begin(), lst.end());

  cout << "Максимальное значение = " << *p << endl;

}

Здесь значением аргумента класса Iterator argument является класс list::iterator, а реализация операций ++, * и != совершенно отличается от массива, хотя ее смысл остается неизменным. Шаблонная функция high() по-прежнему перемещается по данным (в данном случае по объекту класса list) и находит максимальное значение. Мы можем вставлять элементы в любое место списка, так что мы использовали функцию push_front() для добавления элементов в начало списка просто для иллюстрации. С таким же успехом мы могли бы использовать функцию push_back(), как делали это для объектов класса vector.

ПОПРОБУЙТЕ

В стандартном классе vector нет функции push_front(). Почему? Реализуйте функцию push_front() для класса vector и сравните ее с функцией push_back().

Итак, настало время спросить: “А что, если объект класса list будет пустым?” Иначе говоря, “что если lst.begin()==lst.end()?” В данном случае выполнение инструкции *p будет попыткой разыменования элемента, следующего за последним, т.е. lst.end(). Это катастрофа! Или, что еще хуже, в результате можно получить случайную величину, которая исказит правильный ответ.

  Последняя формулировка вопроса содержит явную подсказку: мы можем проверить, пуст ли список, сравнив итераторы begin() и end(), — по существу, мы можем проверить, пуста ли последовательность, сравнивая ее начало и конец.