Итак, рассмотрев мотивы и цели, перейдем к описанию основных определений из библиотеки STL, а затем изучим примеры их применения для более простого создания более совершенного кода для обработки данных.
20.3. Последовательности и итераторы
Основным понятием в библиотеке STL является последовательность. С точки зрения авторов этой библиотеки, любая коллекция данных представляет собой последовательность. Последовательность имеет начало и конец. Мы можем перемещаться по последовательности от начала к концу, при необходимости считывая или записывая значение элементов. Начало и конец последовательности идентифицируются парой итераторов. Итератор (iterator) — это объект, идентифицирующий элемент последовательности.
Последовательность можно представить следующим образом:
Здесь
begin
и
end
— итераторы; они идентифицируют начало и конец последовательности. Последовательность в библиотеке STL часто называют “полуоткрытой” (“half-open”); иначе говоря, элемент, идентифицированный итератором
begin
, является частью последовательности, а итератор
end
ссылается на ячейку, следующую за концом последовательности. Обычно такие последовательности (диапазоны) обозначаются следующим образом:
[begin:end]
. Стрелки, направленные от одного элемента к другому, означают, что если у нас есть итератор на один элемент, то мы можем получить итератор на следующий.
• Что такое итератор? Это довольно абстрактное понятие.
• Итератор указывает (ссылается) на элемент последовательности (или на ячейку, следующую за последним элементом).
• Два итератора можно сравнивать с помощью операторов
==
и
!=
.
• Значение элемента, на который установлен итератор, можно получить с помощью унарного оператора
*
(“разыменование”).
• Итератор на следующий элемент можно получить, используя оператор
++
.
Допустим, что
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).
