Свойства итераторов различных типов

Рассмотрим, какими свойствами обладают итераторы, определенные в библиотеке STL. Этими же свойствами должны обладать итераторы, разработанные отдельно, чтобы быть совместимыми сSTL. Напомним, что посколькуSTL– шаблонная библиотека (т.е. инстанцирование шаблонов происходит на этапе компиляции, а не исполнения), свойство итератора, например иметь операцию переходя к следующему элементу (++) означает лишь, что если есть итераторX, то выражениеX++ - законно; но не означает, что всегда явно определена такая функция. ВыражениеX++ законно и в случае, когдаX– этоint*.

Итак, приведем примеры использования различных классов итераторов, а затем формальные спецификации - «скелеты» классов.

Примечание:

Предполагается, что итератор перебирает элементы коллекции из элементов типа T. Утверждение, написанное в комментариях, предполагает, что при любой реализации итератора оно должно выполняться.

Последовательные итераторы

Использование (куски кода никак не связаны, это лишь сигнатура предоставляемых операций):

ForwardIteratorit;// Конструктор по умолчанию, без аргументов

ForwardIterator it2(it1); // Конструктор копий, it1 и it2 эквивалентны

it2=it1;// Присваивание, it1 и it2 эквивалентны

if(it1==it2) {}// Проверка на равенство выполняется, если

// итераторы указывают на одну и туже позицию,

// или оба являются законечными

if(it1!=it2) {...}// Проверка на неравенство – просто отрицание

// равенства

it2=++it1;// Продвинуть it1; it2=новому значению

it2=it1++;// Продвинуть it1; it2=старому значению

T x=*it1; // Получить значение, указываемого элемента;

// возможно только если it1 предоставляет право

// чтения

*it1=x; // Изменить указываемый элемент; возможно только

// если it1 предоставляет право записи

Скелет класса (это не точное объявление класса итератора из STL, однако оно позволяет понять, какие операции входят в интерфейс итератора):

classForwardIterator

{

public:

ForwardIterator();

// Конструктор копий

ForwardIterator(const ForwardIterator &i);

// Оператор присваивания

ForwardIterator& operator=(const ForwardIterator &i);

// B должен быть преобразуем к типу bool или просто является им

B operator==(const ForwardIterator &i);

B operator!=(const ForwardIterator &i) {return !(i==*this);}

// Операторы инкремента (продвижения, увеличения на единицу).

// Увеличиваемый итератор должен быть действительным (разыменовываемым).

// После увеличения он может быть либо остаться действительным,

// либо приобрести законечное значение.

// Постфиксная форма оператора: x++

// После выполнения a=x++ а будет равно старому значению x

ForwardIterator operator++(int);

// Префиксная форма: ++x

// После выполнения a=++x а будет равно новому значению х.

ForwardIterator&operator++(void);

// Итератор должен быть действительным.

// В зависимости от того, изменяем ли итератор, Q будет:

// Изменяем --> T& (чтобы можно было написать *i=a;)

// Неизменяем --> T или const T& (чтобы нельзя было написать *i=a;

// но можно было - a=*i;)

// где T - указуемый тип

Q operator*();

};