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