Сначала цикл проверяет, не пуст ли диапазон. Если значение итератора 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. Определение и инициализация встроенных массивов
Массив является составным типом (см. раздел 2.3). Оператор объявления массива имеет форму a[d], где а — имя; d — размерность определяемого массива. Размерность задает количество элементов массива, она должна быть больше нуля. Количество элементов — это часть типа массива, поэтому она должна быть известна на момент компиляции. Следовательно, размерность должна быть константным выражением (см. раздел 2.4.4).
unsigned cnt = 42; // неконстантное выражение
constexpr unsigned sz = 42; // константное выражение
// constexpr см. p. 2.4.4
int arr[10]; // массив десяти целых чисел
int *parr[sz]; // массив 42 указателей на int
string bad[cnt]; // ошибка: cnt неконстантное выражение
string strs[get_size()]; // ok, если get_size - constexpr,
// в противном случае - ошибка
По умолчанию элементы массива инициализируются значением по умолчанию (раздел 2.2.1).
Подобно переменным встроенного типа, инициализированный по умолчанию массив встроенного типа, определенный в функции, будет содержать неопределенные значения.
При определении массива необходимо указать тип его элементов. Нельзя использовать спецификатор auto для вывода типа из списка инициализаторов. Подобно вектору, массив содержит объекты. Таким образом, невозможен массив ссылок.
Массив допускает списочную инициализацию (см. раздел 3.3.1) элементов. В этом случае размерность можно опустить. Если размерность отсутствует, компилятор выводит ее из количества инициализаторов. Если размерность определена, количество инициализаторов не должно превышать ее.