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

Итак, рассмотрев мотивы и цели, перейдем к описанию основных определений из библиотеки STL, а затем изучим примеры их применения для более простого создания более совершенного кода для обработки данных.

20.3. Последовательности и итераторы

Основным понятием в библиотеке STL является последовательность. С точки зрения авторов этой библиотеки, любая коллекция данных представляет собой последовательность. Последовательность имеет начало и конец. Мы можем перемещаться по последовательности от начала к концу, при необходимости считывая или записывая значение элементов. Начало и конец последовательности идентифицируются парой итераторов. Итератор (iterator) — это объект, идентифицирующий элемент последовательности.

Последовательность можно представить следующим образом:

Здесь

и — итераторы; они идентифицируют начало и конец последовательности. Последовательность в библиотеке STL часто называют “полуоткрытой” (“half-open”); иначе говоря, элемент, идентифицированный итератором , является частью последовательности, а итератор ссылается на ячейку, следующую за концом последовательности. Обычно такие последовательности (диапазоны) обозначаются следующим образом: . Стрелки, направленные от одного элемента к другому, означают, что если у нас есть итератор на один элемент, то мы можем получить итератор на следующий.

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

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

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

и .

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

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

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

.

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

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

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

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

ПОПРОБУЙТЕ

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

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

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

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

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

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

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

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

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

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

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

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