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

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

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

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

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

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

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

// вычислить итератор на элемент, ближайший к середине вектора 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.24. Переделайте последнее упражнение раздела 3.3.3 с использованием итераторов.

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

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

3.5. Массивы

Массив (array) — это структура данных, подобная библиотечному типу vector (см. раздел 3.3), но с другим соотношением между производительностью и гибкостью. Как и вектор, массив является контейнером безымянных объектов одинакового типа, к которым обращаются по позиции. В отличие от вектора, массивы имеют фиксированный размер; добавлять элементы к массиву нельзя. Поскольку размеры массивов постоянны, они иногда обеспечивают лучшую производительность во время выполнения приложений. Но это преимущество приобретается за счет потери гибкости.

Если вы не знаете точно, сколько элементов необходимо, используйте вектор.

3.5.1. Определение и инициализация встроенных массивов