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