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

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

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

i  ==  3                 i   !=  3            i  =  J

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

Категория итератора

Операции (дополнительно к

г ==Л iI =j, г =j)

Какие

контейнеры

предоставляют

Каким

алгоритмом

используется

входной

х= % ++i, i++

все четыре

find

выходной

*i = x, ++i, i+ +

все четыре

сору (приемник)

прямой

как у входного и выходного сразу

все четыре

replace

двунаправленный

как у прямого и —г, i-

-   все четыре

reverse

произвольного доступа

как у

двунаправленного и i + n,i — n, i +-и, i — n,i<j, i>j, i <=;', i >=;'

массив, vector, deque ('но не list)

sort

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

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

else cout <<  "  after  "  << *—i;

Мог возникнуть вопрос: почему мы не используем выражение *(г - 1) вме­сто *—i, поскольку не было необходимости изменять значение И Теперь мы видим, что выражение i - 1 допустимо только для операторов произ­вольного доступа, тогда как —i поддерживается также двунаправленными итераторами


<< назад вперед >>