3.4. Знакомство с итераторами.

Хотя для доступа к символам строки или элементам вектора можно использовать индексирование, для этого существует и более общий механизм — итераторы (iterator). Как будет продемонстрировано в части II, кроме векторов библиотека предоставляет несколько других видов контейнеров. У всех библиотечных контейнеров есть итераторы, но только некоторые из них поддерживают оператор индексирования. С технической точки зрения тип string не является контейнерным, но он поддерживает большинство контейнерных операций. Как уже упоминалось, и строки, и векторы предоставляют оператор индексирования. У них также есть итераторы.

Как и указатели (см. раздел 2.3.2), итераторы обеспечивают косвенный доступ к объекту. В случае итератора этим объектом является элемент в контейнере или символ в строке. Итератор позволяет выбрать элемент, а также поддерживает операции перемещения с одного элемента на другой. Подобно указателям, итератор может быть допустим или недопустим. Допустимый итератор указывает либо на элемент, либо на позицию за последним элементом в контейнере. Все другие значения итератора недопустимы.

3.4.1. Использование итераторов.

В отличие от указателей, для получения итератора не нужно использовать оператор обращения к адресу. Для этого обладающие итераторами типы имеют члены, возвращающие эти итераторы. В частности, они обладают функциями-членами begin() и end(). Функция-член begin() возвращает итератор, который обозначает первый элемент (или первый символ), если он есть.

// типы b и е определяют компилятор; см. раздел 2.5.2

// b обозначает первый элемент контейнера v, а е - элемент

// после последнего

auto b = v.begin(), е = v.end();

// b и е имеют одинаковый тип

Итератор, возвращенный функцией end(), указывает на следующую позицию за концом контейнера (или строки). Этот итератор обозначает несуществующий элемент за концом контейнера. Он используется как индикатор, означающий, что обработаны все элементы. Итератор, возвращенный функцией end(), называют итератором после конца (off-the-end iterator), или сокращенно итератором end. Если контейнер пуст, функция begin() возвращает тот же итератор, что и функция end(). 

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

Обычно точный тип, который имеет итератор, неизвестен (да и не нужен). В этом примере при определении итераторов b и е использовался спецификатор auto (см. раздел 2.5.2). В результате тип этих переменных будет совпадать с возвращаемыми функциями-членами begin() и end() соответственно. Не будем пока распространяться об этих типах.

Операции с итераторами.

Итераторы поддерживают лишь несколько операций, которые перечислены в табл. 3.6. Два допустимых итератора можно сравнить при помощи операторов == и !=. Итераторы равны, если они указывают на тот же элемент или если оба они указывают на позицию после конца того же контейнера. В противном случае они не равны.

Таблица 3.6. Стандартные операции с итераторами контейнера

*iter	Возвращает ссылку на элемент, обозначенный итератором iter
iter->mem	Обращение к значению итератора iter и выборка члена mem основного элемента. Эквивалент (*iter).mem
++iter	Инкремент итератора iter для обращения к следующему элементу контейнера
--iter	Декремент итератора iter для обращения к предыдущему элементу контейнера
iter1 == iter2 iter1 != iter2	Сравнивает два итератора на равенство (неравенство). Два итератора равны, если они указывают на тот же элемент или на следующий элемент после конца того же контейнера

Подобно указателям, к значению итератора можно обратиться, чтобы получить элемент, на который он ссылается. Кроме того, подобно указателям, можно обратиться к значению только допустимого итератора, который обозначает некий элемент (см. раздел 2.3.2). Результат обращения к значению недопустимого итератора или итератора после конца непредсказуем.

Перепишем программу из раздела 3.2.3, преобразующую строчные символы строки в прописные, с использованием итератора вместо индексирования:

string s("some string");

if (s.begin() != s.end()) { // удостовериться, что строка s не пуста

 auto it = s.begin();       // it указывает на первый символ строки s

 *it = toupper(*it);        // текущий символ в верхний регистр

}

Как и в первоначальной программе, сначала удостоверимся, что строка s не пуста. В данном случае для этого сравниваются итераторы, возвращенные функциями begin() и end(). Эти итераторы равны, если строка пуста. Если они не равны, то в строке s есть по крайней мере один символ.

В теле оператора if функция begin() возвращает итератор на первый символ, который присваивается переменной it. Обращение к значению этого итератора и передача его функции toupper() позволяет перевести данный символ в верхний регистр. Кроме того, обращение к значению итератора it слева от оператора присвоения позволяет присвоить символ, возвращенный функцией toupper(), первому символу строки s. Как и в первоначальной программе, вывод будет таким:

Some string

Перемещение итератора с одного элемента на другой.

Итераторы используют оператор инкремента (оператор ++) (см. раздел 1.4.1) для перемещения с одного элемента на следующий. Операция приращения итератора логически подобна приращению целого числа. В случае целых чисел результатом будет целочисленное значение на единицу больше 1. В случае итераторов результатом будет перемещение итератора на одну позицию.

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

Перепишем программу, изменяющую регистр первого слова в строке, с использованием итератора.

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

// или не встретится пробел

for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)

 *it = toupper(*it); // преобразовать в верхний регистр

Этот цикл, подобно таковому в разделе 3.2.3, перебирает символы строки s, останавливаясь, когда встречается пробел. Но данный цикл использует для этого итератор, а не индексирование.

Цикл начинается с инициализации итератора it результатом вызова функции s.begin(), чтобы он указывал на первый символ строки s (если он есть). Условие проверяет, не достиг ли итератор it конца строки ( s.end()). Если это не так, то проверяется следующее условие, где обращение к значению итератора it, возвращающее текущий символ, передается функции isspace(), чтобы выяснить, не пробел ли это. В конце каждой итерации выполняется оператор ++it, чтобы переместить итератор на следующий символ строки s.

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

Ключевая концепция. Обобщенное программирование. Программисты, перешедшие на язык С++ с языка С или Java, могли бы быть удивлены тем, что в данном цикле for был использован оператор !=, а не <. Программисты С++ используют оператор != исключительно по привычке. По этой же причине они используют итераторы, а не индексирование: этот стиль программирования одинаково хорошо применим к контейнерам различных видов, предоставляемых библиотекой. Как уже упоминалось, только у некоторых библиотечных типов, vector и string, есть оператор индексирования. Тем не менее у всех библиотечных контейнеров есть итераторы, для которых определены операторы == и !=. Однако большинство их итераторов не имеют оператора <. При обычном использовании итераторов и оператора != можно не заботиться о точном типе обрабатываемого контейнера.

Типы итераторов.

Подобно тому, как не всегда известен точный тип size_type элемента вектора или строки (см. раздел 3.2.2), мы обычно не знаем (да и не обязаны знать) точный тип итератора. Как и в случае с типом size_type, библиотечные типы, у которых есть итераторы, определяют типы по имени iterator и const_iterator, которые представляют фактические типы итераторов.

vector<int>::iterator it;        // it позволяет читать и записывать

                                 // в элементы вектора vector<int>

string::iterator it2;            // it2 позволяет читать и записывать

                                 // символы в строку

vector<int>::const_iterator it3; // it3 позволяет читать, но не

                                 // записывать элементы

string::const_iterator it4;      // it4 позволяет читать, но не

                                 // записывать символы

Тип const_iterator ведет себя как константный указатель (см. раздел 2.4.2). Как и константный указатель, тип const_iterator позволяет читать, но не писать в элемент, на который он указывает; объект типа iterator позволяет и читать, и записывать. Если вектор или строка являются константой, можно использовать итератор только типа const_iterator. Если вектор или строка на являются константой, можно использовать итератор и типа iterator, и типа const_iterator.

Терминология. Итераторы и типы итераторов. Термин итератор (iterator) используется для трех разных сущностей. Речь могла бы идти о концепции итератора, или о типе iterator, определенном классом контейнера, или об объекте итератора. Следует уяснить, что существует целый набор типов, связанных концептуально. Тип относится к итераторам, если он поддерживает общепринятый набор функций. Эти функции позволяют обращаться к элементу в контейнере и переходить с одного элемента на другой. Каждый класс контейнера определяет тип по имени iterator, который обеспечивает действия концептуального итератора.

Функции begin() и end().

Тип, возвращаемый функциями begin() и end(), зависит от константности объекта, для которого они были вызваны. Если объект является константой, то функции begin() и end() возвращают итератор типа const_iterator; если объект не константа, они возвращают итератор типа iterator.

vector<int> v;

const vector<int> cv;

auto it1 = v.begin();  // it1 имеет тип vector<int>::iterator

auto it2 = cv.begin(); // it2 имеет тип vector<int>::const_iterator

Зачастую это стандартное поведение желательно изменить. По причинам, рассматриваемым в разделе 6.2.3, обычно лучше использовать константный тип (такой как const_iterator), когда необходимо только читать, но не записывать в объект. Чтобы позволить специально задать тип const_iterator, новый стандарт вводит две новые функции, cbegin() и cend():

auto it3 = v.cbegin(); // it3 имеет тип vector<int>::const_iterator

Подобно функциям-членам begin() и end(), эти функции-члены возвращают итераторы на первый и следующий после последнего элементы контейнера. Но независимо от того, является ли вектор (или строка) константой, они возвращают итератор типа const_iterator.

Объединение обращения к значению и доступа к члену.

При обращении к значению итератора получается объект, на который указывает итератор. Если этот объект имеет тип класса, то может понадобиться доступ к члену полученного объекта. Например, если есть вектор строк, то может понадобиться узнать, не пуст ли некий элемент. С учетом, что it — это итератор данного вектора, можно следующим образом проверить, не пуста ли строка, на которую он указывает:

(*it).empty()

По причинам, рассматриваемым в разделе 4.1.2, круглые скобки в части (*it).empty() необходимы. Круглые скобки требуют применить оператор обращения к значению к итератору it, а к результату применить точечный оператор (см. раздел 1.5.2). Без круглых скобок точечный оператор относился бы к итератору it, а не к полученному объекту.

(*it).empty() // обращение к значению it и вызов функции-члена empty()

              // полученного объекта

*it.empty() // ошибка: попытка вызова функции-члена empty()

            // итератора it,

            // но итератор it не имеет функции-члена empty()

Второе выражение интерпретируется как запрос на выполнение функции-члена empty() объекта it. Но it — это итератор, и он не имеет такой функции. Следовательно, второе выражение ошибочно.

Чтобы упростить такие выражения, язык предоставляет оператор стрелки (arrow operator) (оператор ->). Оператор стрелки объединяет обращение к значению и доступ к члену. Таким образом, выражение it->mem является синоним выражения (*it).mem.

Предположим, например, что имеется вектор vector<string> по имени text, содержащий данные из текстового файла. Каждый элемент вектора — это либо предложение, либо пустая строка, представляющая конец абзаца. Если необходимо отобразить содержимое первого параграфа из вектора text, то можно было бы написать цикл, который перебирает вектор text, пока не встретится пустой элемент.

// отобразить каждую строку вектора text до первой пустой строки

for (auto it = text.cbegin();

 it != text.cend() && !it->empty(); ++it)

 cout << *it << endl;

Код начинается с инициализации итератора it указанием на первый элемент вектора text. Цикл продолжается до тех пор, пока не будут обработаны все элементы вектора text или пока не встретится пустой элемент. Пока есть элементы и текущий элемент не пуст, он отображается. Следует заметить, что, поскольку цикл только читает элементы, но не записывает их, здесь для управления итерацией используются функции cbegin() и cend().

Некоторые операции с векторами делают итераторы недопустимыми.

В разделе 3.3.2 упоминался тот факт, что векторы способны расти динамически. Обращалось также внимание на то, что нельзя добавлять элементы в вектор в цикле серийного оператора for. Еще одно замечание: любая операция, такая как вызов функции push_back(), изменяет размер вектора и способна сделать недопустимыми все итераторы данного вектора. Более подробная информация по этой теме приведена в разделе 9.3.6.

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

3.4.2. Арифметические действия с итераторами.

Инкремент итератора перемещает его на один элемент. Инкремент поддерживают итераторы всех библиотечных контейнеров. Аналогично операторы == и != можно использовать для сравнения двух допустимых итераторов (см. раздел 3.4) любых библиотечных контейнеров.

Итераторы строк и векторов поддерживают дополнительные операции, позволяющие перемещать итераторы на несколько позиций за раз. Они также поддерживают все операторы сравнения. Эти операторы зачастую называют арифметическими действиями с итераторами (iterator arithmetic). Они приведены в табл. 3.7.

Таблица 3.7. Операции с итераторами векторов и строк

iter + n iter - n	Добавление (вычитание) целочисленного значения n к (из) итератору возвращает итератор, указывающий на элемент n позиций вперед (назад) в пределах контейнера. Полученный итератор должен указывать на элемент или на следующую позицию за концом того же контейнера
iter1 += n iter1 -= n	Составные операторы присвоения со сложением и вычитанием итератора. Присваивает итератору iter1 значение на n позиций больше или меньше предыдущего
iter1 - iter2	Вычитание двух итераторов возвращает значение, которое, будучи добавлено к правому итератору, вернет левый. Итераторы должны указывать на элементы или на следующую позицию за концом того же контейнера
>, >=, <, <=	Операторы сравнения итераторов. Один итератор меньше другого, если он указывает на элемент, расположенный в контейнере ближе к началу. Итераторы должны указывать на элементы или на следующую позицию за концом того же контейнера

Арифметические операции с итераторами.

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

// вычислить итератор на элемент, ближайший к середине вектора vi

auto mid = vi.begin() + vi.size() / 2;

Если у вектора vi 20 элементов, то результатом vi.size()/2 будет 10. В данном случае переменной mid будет присвоено значение, равное vi.begin() + 10. С учетом, что нумерация индексов начинаются с 0, это тот же элемент, что и vi[10], т.е. элемент на десять позиций от начала.

Кроме сравнения двух итераторов на равенство, итераторы векторов и строк можно сравнить при помощи операторов сравнения ( <, <=, >, >=). Итераторы должны быть допустимы, т.е. должны обозначать элементы (или следующую позицию за концом) того же вектора или строки. Предположим, например, что it является итератором в том же векторе, что и mid. Следующим образом можно проверить, указывает ли итератор it на элемент до или после итератора mid:

if (it < mid)

 // обработать элементы в первой половине вектора vi

Можно также вычесть два итератора, если они указывают на элементы (или следующую позицию за концом) того же вектора или строки. Результат — дистанция между итераторами. Под дистанцией подразумевается значение, на которое следует изменить один итератор, чтобы получить другой. Результат имеет целочисленный знаковый тип difference_type. Тип difference_type определен и для вектора, и для строки. Этот тип знаковый, поскольку результатом вычитания может оказаться отрицательное значение.

Использование арифметических действий с итераторами.

Классическим алгоритмом, использующим арифметические действия с итераторами, является двоичный поиск (binary search). Двоичный (бинарный) поиск ищет специфическое значение в отсортированной последовательности. Алгоритм работает так: сначала исследуется элемент, ближайший к середине последовательности. Если это искомый элемент, работа закончена. В противном случае, если этот элемент меньше искомого, поиск продолжается только среди элементов после исследованного. Если средний элемент больше искомого, поиск продолжается только в первой половине. Вычисляется новый средний элемент оставшегося диапазона, и действия продолжаются, пока искомый элемент не будет найден или пока не исчерпаются элементы.

Используя итераторы, двоичный поиск можно реализовать следующим образом:

// текст должен быть отсортирован

// beg и end ограничивают диапазон, в котором осуществляется поиск

auto beg = text.begin(), end = text.end();

auto mid = text.begin() + (end - beg)/2; // исходная середина

// пока еще есть элементы и искомый не найден

while (mid != end && *mid != sought) {

 if (sought < *mid) // находится ли искомый элемент в первой половине?

  end = mid;        // если да, то изменить диапазон, игнорируя вторую

                    // половину

 else               // искомый элемент во второй половине

  beg = mid + 1;    // начать поиск с элемента сразу после середины

 mid = beg + (end - beg)/2; // новая середина

}

Код начинается с определения трех итераторов: beg будет первым элементом в диапазоне, end — элементом после последнего, a mid — ближайшим к середине. Инициализируем эти итераторы значениями, охватывающими весь диапазон вектора vector<string> по имени text.

Сначала цикл проверяет, не пуст ли диапазон. Если значение итератора mid равно текущему значению итератора end, то элементы для поиска исчерпаны. В таком случае условие ложно и цикл while завершается. В противном случае итератор mid указывает на элемент, который проверяется на соответствие искомому. Если это так, то цикл завершается.

Если элементы все еще есть, код в цикле while корректирует диапазон, перемещая итератор end или beg. Если обозначенный итератором mid элемент больше, чем sought, то если искомый элемент и есть в векторе, он находится перед элементом, обозначенным итератором mid. Поэтому можно игнорировать элементы после середины, что мы и делаем, присваивая значение итератора mid итератору end. Если значение *mid меньше, чем sought, элемент должен быть в диапазоне элементов после обозначенного итератором mid. В данном случае диапазон корректируется присвоением итератору beg позиции сразу после той, на которую указывает итератор mid. Уже известно, что mid не указывает на искомый элемент, поэтому его можно исключить из диапазона.

В конце цикла while итератор mid будет равен итератору end либо будет указывать на искомый элемент. Если итератор mid равен end, то искомого элемента нет в векторе text.

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

Упражнение 3.24. Переделайте последнее упражнение раздела 3.3.3 с использованием итераторов.

Упражнение 3.25. Перепишите программу кластеризации оценок из раздела 3.3.3 с использованием итераторов вместо индексации.

Упражнение 3.26. Почему в программе двоичного поиска использован код mid = beg + (end - beg) / 2;, а не mid = (beg + end) / 2;?