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

// текст должен быть отсортирован

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

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

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

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

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

Массив является составным типом (см. раздел 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) элементов. В этом случае размерность можно опустить. Если размерность отсутствует, компилятор выводит ее из количества инициализаторов. Если размерность определена, количество инициализаторов не должно превышать ее.

Если размерность больше количества инициализаторов, то инициализаторы используются для первых элементов, а остальные инициализируются по умолчанию (см. раздел 3.3.1):

const unsigned sz = 3;

int ia1[sz] = {0, 1, 2}; // массив из трех целых чисел со

// значениями 0, 1, 2

int a2[] = {0, 1, 2}; // массив размером 3 элемента

int a3[5] = {0, 1, 2}; // эквивалент a3[] = {0, 1, 2, 0, 0}

string a4[3] = {"hi", "bye"}; // эквивалент a4[] = {"hi", "bye", ""}

int a5[2] = {0, 1, 2}; // ошибка: слишком много инициализаторов

У символьных массивов есть дополнительная форма инициализации: строковым литералом (см. раздел 2.1.3). Используя эту форму инициализации, следует помнить, что строковые литералы заканчиваются нулевым символом. Этот нулевой символ копируется в массив наряду с символами литерала.

char a1[] = {'C', '+', '+'}; // списочная инициализация без

// нулевого символа

char а2[] = {'C', '+', '+', '\0'}; // списочная инициализация с явным

// нулевым символом

char a3[] = "С++"; // нулевой символ добавляется

// автоматически

const char a4[6] = "Daniel"; // ошибка: нет места для нулевого

// символа!

Массив a1имеет размерность 3; массивы а2и a3— размерности 4. Определение массива a4ошибочно. Хотя литерал содержит только шесть явных символов, массив a4должен иметь по крайней мере семь элементов, т.е. шесть для самого литерала и один для нулевого символа.