Язык программирования C++. Пятое издание

Кроме сравнения двух итераторов на равенство, итераторы векторов и строк можно сравнить при помощи операторов сравнения (<, <=, >, >=). Итераторы должны быть допустимы, т.е. должны обозначать элементы (или следующую позицию за концом) того же вектора или строки. Предположим, например, что 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 по имени 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 с использованием итераторов вместо индексации.