Если бы мы хотели, чтобы числа шли в порядке возрастания, их нужно было бы перечислить в таком порядке в заданных массивах а п b и, кроме того, заменить определение оператора меньше . Поскольку числа и так уже расположены в порядке возрастания в обоих массивах, нам остается только вместо функции-члена operator использовать следующую:

bool operator<(const entry &b) const

{ return nr < b.r;

После этой модификации вывод программы будет содержать числа в восходящем порядке:

10 Betty

11 James 16 Fred

20 William 80 Jim

Функция operator не обязана быть членом класса entry. Иными словами, мы могли бы написать

struct entry { long nr; char name[30];

bool operator<( const entry &a, const entry &b) const

{ return strcmp(a.name, b.name) < 0;

вместо того определения класса entry, которое приводится в программе merge2.cpp. Кстати, в разделе 7.3.7 мы увидим, что существует версия merge, которая позволяет нам задать функцию сравнения в виде аргумента.

1.9. Категории итераторов

Как видно из раздела 1.4, мы можем использовать алгоритм sort д,ля массивов, векторов и двусторонних очередей, но не для списков. Алгоритм find, напротив, может быть использован для всех четырех типов контейнеров. (В этом разделе воспользуемся термином контейнер, имея в виду последовательный контейнер, игнорируя при этом другие типы контейнеров, которые обсудим в главах 2 и 4.) Ясно, что для нахождения заданного значения достаточно одного перебора всех элементов, тогда как эффективная сортировка требует наличия произвольного доступа. В обоих случаях используются итераторы, но алгоритм sort требует более мощных итераторов,

нежели алгоритм find. Итераторы можно естественным образом поделить на пять категорий, в соответствии с теми операциями, которые для них определены. Предположим, что i nj - итераторы одного вида. Тогда три следующие операции

i == 3 i = 3 i = J

возможны всегда, независимо от категории этих итераторов. Следующая таблица показывает, какие из операций применимы к каждой из категорий итераторов; мы предполагаем, что х является переменной того же типа, что и элементы рассматриваемого контейнера, an - переменная типа int.

Как указано во втором столбце таблицы, прямой (forward) итератор поддерживает все операции как входных {input), так и выходных {output) итераторов. Двунаправленные {bidirectional) итераторы в дополнение ко всем операциям, поддерживаемым прямыми итераторами, поддерживают операции префиксного и постфиксного уменьшения. Добавив к этому набор операций +, -, +=, -=, <, >, <=, >=, мы приходим к категории итераторов произвольного доступа {random access). Добавление целого числа к итератору возможно только для итераторов произвольного доступа; эта операция требуется, к примеру, для алгоритма сортировки. Так как список не предоставляет итераторов произвольного доступа, мы не можем применить к списку алгоритм sort.

Программа find\ в разделе 1.5 содержит строчку

else cout after *-i;

Мог возникнуть вопрос: почему мы не используем выражение *{i - 1) вместо *-i, поскольку не было необходимости изменять значение г? Теперь мы видим, что выражение i - 1 допустимо только для операторов произвольного доступа, тогда как -i поддерживается также двунаправленными итераторами. В нынешнем варианте программа findi основана на векторе, а поскольку вектор работает с итераторами произвольного доступа, запись *(г- 1) не создаст проблем. Однако проблемы появятся, если слово vector везде, где оно встречается в программе, заменить на list. В этом случае переменная i станет двунаправленным итератором, для которого выражение г - 1 не является допустимым. Другими словами, программа findi перестанет компилироваться, если мы одновременно заменим vector на list, а*-i на *(i - 1). Точно так же и для итераторов, определенных классом list, недоступна операция сравнения меньше чем . Это иллюстрирует комментарий в следующем фрагменте:

Демонстрация итераторов произвольного доступа: int а[3] = {5, 8, 2}; vector<int> v(a, а+3);

vector<int>: : iterator iv = v.beginO, ivl;

ivl = iv + 1;

bool bl = iv < ivl;

В двух последних строчках + и < допустимы, поскольку iv и ivl - итераторы произвольного доступа.

Демонстрация двунаправленных итераторов: list<int> w(a, а+3);

list<int>: : iterator iw = w.beginO, iwl;

iwl = iw + 1; Ошибка

bool b2 = iw < iwl; Ошибка

В двух последних строчках + и < недопустимы, поскольку iw и iwl - двунаправленные итераторы. Следующие две строчки, напротив, являются правильными: iwl = iw;

bool ЬЗ = iw == iwl;

Какие категории итераторов требуются для алгоритмов

Алгоритм/гий? (рассмотренный в разделе 1.5) из всех операций над итераторами требует исключительно те, которые определены для входных итераторов, потому что ему достаточно только читать элементы последовательности, исполняя, например, операцию присваивания х = *i. Поэтому в вышеприведенной