9.2.1. Итераторы

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

За одним исключением контейнерные итераторы поддерживают все функции, перечисленные в табл. 3.6. Исключение в том, что итераторы контейнера forward_list не поддерживают оператор декремента (--). Операторы арифметических действий с итераторами, перечисленными в табл. 3.7, применимы только к итераторам контейнеров string, vector, deque и array. К итераторам контейнеров любых других типов эти операторы неприменимы.

Диапазоны итераторов

Диапазон итераторов (iterator range) обозначается парой итераторов, каждый из которых указывает на элемент или на следующий элемент после последнего в том же контейнере. Эти два итератора, обозначающие диапазон элементов контейнера, зачастую называют begin и end или, что несколько обманчиво, first и last.

Хоть имя last и общепринято, оно немного вводит в заблуждение, поскольку второй итератор никогда не указывает на последний элемент диапазона. Вместо этого он указывает на позицию следующего элемента после последнего. Диапазон включает элемент, обозначенный итератором first, и все элементы от него до обозначенного итератором last, но не включая его.

Такой диапазон элементов называется интервал, включающий левый элемент (left-inclusive interval). Вот стандартная математическая форма записи такого диапазона:

[ begin, end )

Это указывает, что диапазон начинается с элемента, обозначенного итератором begin, и заканчивается элементом перед тем, который обозначен итератором end. Итераторы begin и end должны относиться к тому же контейнеру. Итератор end может быть равен итератору begin, но не должен указывать на элемент перед обозначенным итератором begin.

Требования к итераторам, формирующим диапазон

Два итератора, begin и end, позволяют задать диапазон при следующих условиях.

• Итераторы относятся к существующим элементам или к следующему элементу за концом того же контейнера.

• Элемент end достижим благодаря последовательному приращению итератора begin. Другими словами, итератор end не должен предшествовать итератору begin.

Смысл использования диапазонов, включающих левый элемент

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

• Если итератор begin равен итератору end, то диапазон пуст.

• Если итератор begin не равен итератору end, в диапазоне содержится по крайней мере один элемент и итератор begin указывает на первый из них.

• Можно осуществлять инкремент итератора begin до тех пор, пока он не станет равен итератору end (т.е. begin == end).

Благодаря этим качествам можно создавать вполне безопасные циклы обработки диапазона элементов, например, такие:

while (begin != end) {

 *begin = val; // ok: диапазон не пуст, begin обозначает элемент

 ++begin;      // переместить итератор и получить следующий элемент

}

Если итераторы begin и end задают допустимый диапазон элементов, выполнение условия begin == end означает, что диапазон пуст. В данном случае это условие выхода из цикла. Если диапазон не пуст, значит, итератор begin указывает на элемент в этом не пустом диапазоне. Вполне очевидно, что в теле цикла while можно безопасно обращаться к значению итератора begin, поскольку оно гарантировано существует. И наконец, поскольку инкремент итератора begin осуществляется в теле цикла, последний гарантированно будет конечным.

Упражнения раздела 9.2.1

Упражнение 9.3. Каким условиям должны удовлетворять итераторы, обозначающие диапазон?

Упражнение 9.4. Напишите функцию, которая получает два итератора вектора vector<int> и значение типа int. Организуйте поиск этого значения в диапазоне и возвратите логическое значение (тип bool), указывающее, что значение найдено.

Упражнение 9.5. Перепишите предыдущую программу так, чтобы она возвращала итератор на найденный элемент. Функция должна учитывать случай, когда элемент не найден.

Упражнение 9.6. Что не так со следующей программой? Как ее можно исправить?

list<int> lst1;

list<int>::iterator iter1 = lst1.begin(),

iter2 = lst1.end();

while (iter1 < iter2) /* ... */