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

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

• Что такое итератор? Это довольно абстрактное понятие.

• Итератор указывает (ссылается) на элемент последовательности (или на ячейку, следующую за последним элементом).

• Два итератора можно сравнивать с помощью операторов

==
и
!=
.

• Значение элемента, на который установлен итератор, можно получить с помощью унарного оператора

*
(“разыменование”).

• Итератор на следующий элемент можно получить, используя оператор

++
.

Допустим, что

p
и
q
— итераторы, установленные на элементы одной и той же последовательности.

Очевидно, что идея итератора связана с идеей указателя (см. раздел 17.4). Фактически указатель на элемент массива является итератором. Однако многие итераторы являются не просто указателями; например, мы могли бы определить итератор с проверкой выхода за пределы допустимого диапазона, который генерирует исключение при попытке сослаться за пределы последовательности

[begin:end]
или разыменовать итератор
end
. Оказывается, что итератор обеспечивает огромную гибкость и универсальность именно как абстрактное понятие, а не как конкретный тип. В этой и следующей главах при приведем еще несколько примеров.

ПОПРОБУЙТЕ

Напишите функцию

void copy(int* f1, int* e1, int* f2)
, копирующую элементы массива чисел типа
int
, определенного последовательностью
[f1:e1]
в другую последовательность
[f2:f2+(e1–f1)]
. Используйте только упомянутые выше итераторы (а не индексирование).

Итераторы используются в качестве средства связи между нашим кодом (алгоритмами) и нашими данными. Автор кода знает о существовании итераторов (но не знает, как именно они обращаются к данным), а поставщик данных предоставляет итераторы, не раскрывая всем пользователям детали механизма хранения данных. В результате получаем достаточно независимые друг от друга алгоритмы и контейнеры. Процитируем Алекса Степанова: “Алгоритмы и контейнеры библиотеки STL потому так хорошо работают друг с другом, что ничего не знают друг о друге”. Вместо этого и алгоритмы, и контейнеры знают о последовательностях, определенных парами итераторов.

Иначе говоря, автор кода больше не обязан ничего знать о разнообразных способах хранения данных и обеспечения доступа к ним; достаточно просто знать об итераторах. И наоборот, если поставщик данных больше не обязан писать код для обслуживания огромного количества разнообразных пользователей, ему достаточно реализовать итератор для данных. На базовом уровне итератор определен только операторами

*
,
++
,
==
и
!=
. Это обеспечивает его простоту и быстродействие.

Библиотека STL содержит около десяти контейнеров и 60 алгоритмов, связанных с итераторами (см. главу 21). Кроме того, многие организации и отдельные лица создают контейнеры и алгоритмы в стиле библиотеки STL. Вероятно, библиотека STL в настоящее время является наиболее широко известным и широко используемым примером обобщенного программирования (см. раздел 19.3.2). Если вы знаете основы и несколько примеров, то сможете использовать и все остальное.

20.3.1. Вернемся к примерам

Посмотрим, как можно решить задачу “найти максимальный элемент” с помощью последовательности STL.

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;

}

Обратите внимание на то, что мы исключили локальную переменную

h
, которую до сих пор использовали для хранения максимального элемента. Если вам неизвестен реальный тип элементов последовательности, то инициализация
–1
выглядит совершенно произвольной и странной. Она действительно является произвольной и странной! Кроме того, такая инициализация представляет собой ошибку: в нашем примере число
1
оправдывает себя только потому, что отрицательных скоростей не бывает. Мы знаем, что “магические константы”, такие как
–1
, препятствуют сопровождению кода (см. разделы 4.3.1, 7.6.1, 10.11.1 и др.). Здесь мы видим, что такие константы могут снизить полезность функции и свидетельствовать о неполноте решения; иначе говоря, “магические константы” могут быть — и часто бывают — свидетельством небрежности.

Обобщенную функцию

high
можно использовать для любых типов элементов, которые можно сравнивать с помощью операции
<
. Например, мы могли бы использовать функцию
high
для поиска лексикографически последней строки в контейнере
vector<string>
(см. упр. 7).

Шаблонную функцию

high
можно применять к любой последовательности, определенной парой итераторов. Например, мы можем точно воспроизвести нашу программу.

double* get_from_jack(int* count); // Джек вводит числа типа double