Итераторы

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

Внутренняя организация: все алгоритмы для последовательностей в MPL реализованы в терминах итераторов, что позволяет использовать их для пользовательских последовательностей времени компиляции, которые поддерживают соответсвующие интерфейсы итераторов.

Концепции

Все итераторы в MPL делятся на три категории, названые в соответствии с типом обхода. Категории:

• Прямой итератор;

• Двунаправленный итератор;

• Итератор произвольного доступа;

Концепции организованы в иерархическом порядке: итератор произвольного доступа доступа является специализацией двунаправленного итератора, который, в свою очередь, является специализацией прямого итератора.

Forward Iterator

(Прямой итератор)

Описание:

Прямой итератор i это тип, который ссылается на позицию элемента в прямой последовательности. Обеспечивает доступ к элементу посредством операции разыменования, а также предоставляет способ получения итератора на следующий элемент в данной последовательности.

Определения:

• Итератор может быть разыменовыван:

deref<i>::type

• Итератор, следующий за последним элементом последовательности не может быть разыменован.

• Итератор i может быть инкрементирован:

next<i>::type

• Итератор, следующий за последним элементом последовательности не может быть инкрементирован.

• Два итераторы в одной последовательности эквивалентны, если они имеют одинаковый тип.

• Итератор j достижим из итератора i, если, после рекурсивного применения к i метафункции next конечное число раз, i эквиваленен j.

• Обозначение [i, j) указывает диапазон из итераторов, от i (включительно) до j (не включительно).

• Диапазон [i, j) является действительным диапазоном, если j доступен из i.

Требования к выражениям:

Выражение	Тип	Сложность
deref<i>::type	Любой тип	Амортизированное постоянное время.
next<i>::type	Прямой итератор	Амортизированное постоянное время.
i::category	Интегральная константа, преобразуемая к forward_iterator_tag	Постоянное время.

Семантика выражений:

typedef deref<i>::type j;

Предусловие: i – тип, который может быть разыменован.

Семантика: j – идентичен типу элемента, на который указывает итератор.

typedef next<i>::type j;

Предусловие: i может быть инкрементирован.

Семантика: j – следующий итератор в последовательности.

Постусловие: j – разыменованный итератор или итератор, указывающий на элемент следующий за последним.

typedef i::category c;

Семантика: c идентична тэгу категории итератора.

Инварианты:

Для любых прямых итераторов i и j всегда поддерживаются следующие инварианты:

• i и j эквивалентны, если и только если они указывают на один и тот же элемент.

• Если разыменованный итератор i эквивалентен j, то j также разыменованный итератор.

• Если i и j эквивалентны и разыменовываны, то

deref<i>::type

идентичен

deref<j>::type

• Если инкрементированный итератор i эквивалентен j, то j также инкрементированный итератор.

• Если i и j эквивалентны и инкрементированы, то

next<i>::type

идентичен

next<j>::type

Смотри также:

Iterators, Bidirectional Iterator, Forward Sequence, deref, next

Bidirectional Iterator