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

Страуструп Бьерн
Шрифт:

{ 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;

}

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

list
.

void f

{

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
. Это катастрофа! Или, что еще хуже, в результате можно получить случайную величину, которая исказит правильный ответ.

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

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

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? Сначала опишем схему решения (игнорируя для простоты распределители памяти), а затем объясним ее.