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

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

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

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

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

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

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

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

Если у вектора vi20 элементов, то результатом 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). Двоичный (бинарный) поиск ищет специфическое значение в отсортированной последовательности. Алгоритм работает так: сначала исследуется элемент, ближайший к середине последовательности. Если это искомый элемент, работа закончена. В противном случае, если этот элемент меньше искомого, поиск продолжается только среди элементов после исследованного. Если средний элемент больше искомого, поиск продолжается только в первой половине. Вычисляется новый средний элемент оставшегося диапазона, и действия продолжаются, пока искомый элемент не будет найден или пока не исчерпаются элементы.