Лекция 13

Свойства, которыми должен обладать итератор:

• нужно иметь возможность разыменования итератора. Для того, чтобы получить доступ к значению, на которое ссылается итератор. (перегрузка *)

• должна существовать возможность присваивания одного итератора другому (перегрузка =)

• должна существовать возможность сравнения одного оператора с другим (перегрузка == и !=)

• должна существовать возможность перемещения итераторов по элементам контейнеру (перегрузка ++ и --)

Итератор может решить и другие задачи, но не одна из них не является обязательной. STL определяет несколько уровней итераторов с возрастающими возможностями. Обычный указатель соответствует требованиям, предъявляемым итератору.

Для разграничения префиксной и постфиксной операции инкрементация принято соглашение о том, что оператор ++ без аргументов – это префиксная форма, оператор ++(int) – постфиксная форма инкрементации. При этом аргумент в постфиксной форме никогда не используется и не нуждается в именовании. Библиотека STL поддерживает требование наличия дополнительного аргумента за последним значимым элементом.

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

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

Определяя для каждого класса соответствующий итератор и создавая классы в унифицированной манере, STL позволяет писать один и тот же код для контейнеров, которые имеют совершенно разное представление. Автоматическое выведение типа type inference позволяют не указывать тип создаваемого итератора, а делегировать выполнение этого действия на исполняющую среду.

Работа с STL начинается с определения алгоритма обработки контейнера, который необходимо выразить максимально обобщенным образом, обеспечивая независимость от типа данных и типа контейнера. Для обеспечения работы обобщенного алгоритма со специфическими случаями определяются итераторы, соответствующие нуждам алгоритма, и закладываются требования в архитектуру самого контейнера. Базовые свойства итераторов и контейнеров вытекают из требований, заложенных алгоритмом.

Виды итераторов

Алгоритм find операции ++ так, чтобы оператор мог пошагово проходить весь контейнер. Алгоритму find нужен доступ к файлам для чтения, но не для записи, он просто просматривает данные контейнера, не изменяя их. Алгоритм сортировки требует произвольного доступа, чтобы иметь возможность обмена значениями неверно расположенных элементов. Если iter – итератор, то произвольный доступ можно получить, определив операцию +. для того, чтобы можно было написать выражение iter+10.Кроме того, алгоритм должен иметь возможность читать данные и записывать их. В библиотеке STL определены 5 типов операторов и описаны алгоритмы в терминах разновидности итераторов:

• входной (input)

• выходной (output)

• однонаправленный (forward)

• двунаправленный (bidirectional)

• произвольного доступа (random-access)

Прототип алгоритма find говорит о том, что ему необходимо для входных параметров 2 итератора. Прототип функции sort указывает, что алгоритм нуждается в итераторе произвольного доступа. Все 5 видов итераторов можно разыменовывать, т.е для них определена операция разыменования. Можно сравнивать эти итераторы на эквивалентность (==), неэквивалентность (!=). Если 2 итератора эквивалентны, то разыменование одного из них должно порождать то же значение, что и разыменование другого. Эти свойства истинны как для встроенных операций и указателей и должны быть выполнены при создании собственных классов итераторов.