Как написать свой итератор

Необходимость написания собственных итераторов или адаптеров возникает в случае, если есть необходимость использовать алгоритмы STLдля собственных коллекций, не предусмотренных вSTL– например, бинарных деревьев, данных от устройств и т.п.

Еще одна причина – необходимость дополнительной обработки при просмотре элементов. Например, можно встроить в итератор возможность помечания просматриваемых элементов или ведение журнала просмотренных элементов – и все это без изменений в коде, использующем итератор. Вообще-то такое расширение итератора – перегрузка его функциональности и лучше было бы реализовать ее отдельно, однако в некоторых случаях это может быть гораздо удобнее.

Практически единственное, но обязательное требование к итератору – он должен реализовывать интерфейс определенный для заданного типа итератора. Кроме того, категория итератора должна соответствовать сути итерируемого объекта – так, для итератора данных от устройства следует выбрать категорию итератора ввода, и т.п. – см. часть «Классификация итераторов».

Следует помнить, что итератор – такой же объект, как и любой другой, и вполне возможно добавить в него дополнительную функциональность помимо предусмотренной требованиями (но не нарушающую их). Например, передавать какие-нибудь аргументы конструктору итератора – скажем, для итератора, ведущего журнал просмотра элементов передавать имя файла, в котором будет вестись журнал.

Для того, чтобы написанный итератор был совместим с STL, для него должны быть определены теги и характеристики, т.е. необходимо существование класса iterator_traits<CMyIterator>, где CMyIterator – создаваемый класс итератора

Для обеспечения этого можно: а)унаследовать его от существующего класса итератора, б) унаследовать от какого-либо iterator_traits, либо в)написать нужные характеристики самим. Первый путь применим, когда требуется частично или полностью сохранить функциональность наследуемого класса итератора, второй – когда схожей функциональности не требуется, но требуется удовлетворение какому-либо стандартному набору характеристик (traits), третий – когда набор характеристик не совпадает ни с одним из существующих вSTL.

Попробуем написать и использовать простой итератор. Пусть, скажем, это будет итератор данных от какого-то устройства (устройство будет незатейливо симулироваться генератором целых случайных чисел в небольшом диапазоне), а законечным значением итератора будет считаться нулевое значение сигнала.

Это, очевидно, итератор ввода (input iterator).

#include <stdlib.h>

#include <time.h>

#include <iostream>

#include <iterator>

#include <utility>

using namespace std;

classDeviceIterator :public input_iterator

{

intvalue;

/*

* Для обеспечения условия "равны только копии,

* а также все законечные" введем механизм

* идентификаторов.

* У двух итераторов, являющихся копиями одного

* и того же, идентификаторы будут равны, у

* остальных - нет.

* Поскольку после продвижения итератора он должен

* перестать быть равен какому-либо другому итератору,

* создадим глобальную функцию генерации уникальных

* идентификаторов genId(), которая будет

* гарантированно возвращать еще не использовавшийся

* идентификатор.

*/

// Идентификатор

intid;

// Текущий максимальный идентификатор: глобальная переменная для класса

staticintmaxId;

// Максимально возможное значение сигнала при симуляции

enum{maxSignal=12};

public:

// Сгенерировать уникальный идентификатор

static int genId() {return ++maxId;}

int getId() const {return id;}

// Законечный итератор с нулевым значением сигнала

DeviceIterator() :value(0),id(genId()) {}

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

// При копировании копируется идентификатор и итераторы остаются

// равными до тех пор, пока один из них не изменит свой ID в результате

// присваивания или продвижения

DeviceIterator(const DeviceIterator &i)

:value(*i), id(i.getId()) {}

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

// Аналогичное замечание.

DeviceIterator& operator=(const DeviceIterator &i)

{

value=*i;

id=i.getId();

return *this;

}

bool operator==(const DeviceIterator &i)

{

// Считаем все законечные итераторы равными.

if(!value)return(*i==0);

// В противном случае равны те, у которых равны ID

return id==i.getId();

}

bool operator!=(const DeviceIterator &i)

{

return !(*this==i);

}

DeviceIterator& operator++(void)

{

// "получить" новые данные от устройства

value=rand()%maxSignal;

// Устранить возможность равенства какому-либо другому итератору

id=genId();

return *this;

}

void operator++(int)

{

// Аналогично

value=rand()%maxSignal;

id=genId();

}

const int& operator*() const {return value;}

};

int DeviceIterator::maxId=0;

intmain() {

DeviceIterator i1,i2;

srand(time(NULL));

cout<<((i1==i2)?"Equal":"Unequal")<<endl; // Два законечных - равны

++i1;

cout<<((i1==i2)?"Equal":"Unequal")<<endl;// Законечный и любой другой – не равны

i2=i1;

cout<<((i1==i2)?"Equal":"Unequal")<<endl; // Копии равны

++i1;

++i2;

cout<<((i1==i2)?"Equal":"Unequal")<<endl;// После изменения итераторы не равны

i2=DeviceIterator();

while(++i1 != i2) {

cout<<(*i1)<<endl;

}

return 0;

}

Вывод программы:

Equal

Unequal

Equal

Unequal

1

6

1

5

10

6

10

5

4

7

11

Итератор работает так, как и ожидалось – как и должен работать корректный итератор ввода.

1Коллекция – синоним контейнера – объект, который хранит другие объекты.

2Итераторы этого типа предоставляются контейнеромlist

3Итераторы этого типа предоставляются контейнерамиvectorиdeque

4Стандартные алгоритмы рассматриваются в одной из следующих работ

5Эта и следующая главы содержат более глубокие знания о итераторахSTLи не являются необходимыми для простого использования итераторов