совершенно отличается от массива, хотя ее смысл остается неизменным. Шаблонная функция
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? Сначала опишем схему решения (игнорируя для простоты распределители памяти), а затем объясним ее.
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;
// ...
};
Оператор
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++).
В стандарте класс
list
и другие стандартные контейнеры определены аналогично. Рассмотрим пример.
template<class Elem> 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).