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

{

  list<int> lst;

  int x;

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

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

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

}

Здесь значением аргумента класса

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

ПОПРОБУЙТЕ

В стандартном классе

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

Итак, настало время спросить: “А что, если объект класса

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

 

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

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

Существует важная причина, по которой итератор

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

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

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

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

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

else

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

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

20.5. Еще одно обобщение класса vector

Из примеров, приведенных в разделах 20.3 и 20.4, следует, что стандартный вектор имеет член класса, являющийся классом

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

template<class T> 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();

  // ...

};

 

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

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

и

for (vector<int>::size_type i = 0; i<v.size(); ++i)

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

Дело в том, что, для того, чтобы написать эти инструкции, нам на самом деле не обязательно знать, какие именно типы называются

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