Программирование полностью

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

В нашем примере можно поступить следующим образом:

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

if (p==lst.end())         // мы достигли конца?

  cout << "Список пустой";

else

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

Работая с алгоритмами из библиотеки STL, мы систематически используем эту проверку. Поскольку в стандартной библиотеке список предусмотрен, не будем углубляться в детали его реализации. Вместо этого кратко укажем, чем эти списки удобны (если вас интересуют детали реализации списков, выполните упр. 12–14).

Из примеров, приведенных в разделах 20.3 и 20.4, следует, что стандартный вектор имеет член класса, являющийся классом iterator, а также функции-члены begin() и end() (как и класс std::list). Однако мы не указали их в нашем классе vector в главе 19. Благодаря чему разные контейнеры могут использоваться более или менее взаимозаменяемо в обобщенном программировании, описанном в разделе 20.3? Сначала опишем схему решения (игнорируя для простоты распределители памяти), а затем объясним ее.

template class vector {

public:

  typedef unsigned long size_type;

  typedef T value_type;

  typedef T* iterator;

  typedef const T* const_iterator;

  // ...

  iterator begin();

  const_iterator begin() const;

  iterator end();

  const_iterator end() const;

  size_type size();

  // ...

};

  Оператор typedef создает синоним типа; иначе говоря, для нашего класса vector имя iterator — это синоним, т.е. другое имя типа, который мы решили использовать в качестве итератора: T*. Теперь для объекта v класса vector можно написать следующие инструкции:

vector::iterator p = find(v.begin(), v.end(),32);

и

for (vector::size_type i = 0; i

 cout << v[i] << '\n';

Дело в том, что, для того, чтобы написать эти инструкции, нам на самом деле не обязательно знать, какие именно типы называются iterator и size_type. В частности, в приведенном выше коде, выраженном через типы iterator и size_type, мы будем работать с векторами, в которых тип size_type — это не unsigned long (как во многих процессорах встроенных систем), а тип iterator — не простой указатель, а класс (как во многих широко известных реализациях языка C++).

В стандарте класс list и другие стандартные контейнеры определены аналогично. Рассмотрим пример.

template class list {

public:

  class Link;

  typedef unsigned long size_type;

  typedef Elem value_type;

  class iterator;        // см. раздел 20.4.2

  class const_iterator;  // как iterator, но допускает изменение

                         // элементов

  // ...

  iterator begin();

  const_iterator begin() const;

  iterator end();

  const_iterator end() const;

  size_type size();

  // ...

};

Таким образом, можно писать код, не беспокоясь о том, что он использует: класс list или vector. Все стандартные алгоритмы определены в терминах этих имен типов, таких как iterator и size_type, поэтому они не зависят от реализации контейнеров или их вида (подробнее об этом — в главе 21).

  Важным свойством списка является возможность вставлять и удалять элементы без перемещения других элементов списка. Исследуем простой пример, иллюстрирующий этот факт. Посмотрим, как представить символы в текстовом документе в простом текстовом редакторе. Это представление должно быть таким, чтобы операции над документом стали простыми и по возможности эффективными.