категории итераторов

• итератор ввода (input iterator) - используется потоками ввода;
• итератор вывода (output iterator) - используется потоками вывода;
• однонаправленный итератор (forward iterator) - для прохода по элементам в одном направлении;
• двунаправленный итератор (bidirectional iterator) - способен пройтись по элементам в любом направлении. Такие итераторы реализованы в некоторых контейнерных типах stl (list, set, multiset, map, multimap);
• итераторы произвольного доступа (random access) - через них можно иметь доступ к любому элемента. Такие итераторы реализованы в некоторых контейнерных типах stl (vector, deque, string, array).

операции доступные итераторам

Кроме операций для итераторов определены три функции:

• advance (InIt& pos, dist n) - перемещает итератор на указанную дистанцию;
• dist distance (InIt pos1, InIt pos2) - вычисляет дистанцию между двумя итераторами;
• iter_swap (FIt1 pos1, FIt2 pos2) - обменивает значения указанных итераторов.

класс iterator_traits

Все характеристики итератора собраны в классе iterator_traits.

template <class T>
struct iterator_traits {
 typedef typename T::value_type value_type; // тип значения элемента
 typedef typename T::difference_type difference_type; // тип разности итераторов
 typedef typename T::iterator_category iterator_category; // категория
 typedef typename T::pointer pointer; // тип указателя
 typedef typename T::reference reference; // тип ссылки
};

Для указания типа итератора, определены пять пустых типов меток.

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag {};
struct bidirectional_iterator_tag: public forward_iterator_tag {};
struct random_access_iterator_tag: public bidirectional_iterator_tag {};

Также определена специализация шаблона iterator_traits, позволяющая использовать обычные указатели в качестве итераторов.

пользовательский итератор

Пользовательские итераторы создаются как наследники от шаблона класса iterator. Для использования итератора в алгоритмах stl определяются указанные выше операции (по необходимости перегружаются и те три функции).

#include <iterator>

// type - имя типа элементов
// с которыми будет работать итератор
class MyIt: 
 public std::iterator 
 <std::bidirectional_iterator_tag, type> {
 ...
};

// а можно задать все детально
class MyIterator: 
 public std::iterator 
 <std::bidirectional_iterator_tag,
 type, ptrdiff_t, type*, type&> {
 ...
};

пример итератора

В С++ двухмерный массив часто представляют в виде одномерного, используя для индексации по x и y формулу x+y*w, где w ширина массива. Ниже приведен простой неоптимизированный итератор работающий с подобными массивами. В качестве объекта массива может выступать любой контейнерный тип с операцией индексации.

С помощью этого итератора вы можете работать с 'окнами' внутри двухмерного массива. Так здесь с помощью fill заполняется окно 3x3 с координатами (2,2) внутри массива 10x10.

#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

// T - тип объекта, содержащего элементы
// Tval - тип элементов
template <typename T,typename Tval>
class It2d: public std::iterator
 <std::forward_iterator_tag, T> {
protected:
T& datab; // объект с элементами, и с операцией[]
int posbeg; // с какого элемента
int width; // полная ширина
int w; // ширина окна
int i; // текущая позиция

public:
It2d(T& ddatab, int pposbeg, int wwidth,
 int ww, int pos=0): datab(ddatab){
width=wwidth;
w=ww;
posbeg=pposbeg;
i=pos;
}


It2d(const It2d<T,Tval>& a):datab(a.datab){
width=a.width;
w=a.w;
i=a.i;
posbeg=a.posbeg;
}

//----------------------------------
Tval& operator *(){
 return datab[posbeg+i%w+i/w*width];
 }

It2d<T,Tval>&operator ++(){
 ++i;
 return *this;
 }

It2d<T,Tval>& operator ++(int a){
 ++i;
 return *this;
 }

bool operator ==(It2d<T,Tval> &it){
return datab==it.datab && i==it.i &&
 w==it.w && width==it.width;
}

bool operator !=(It2d<T,Tval>&it){
 return !(*this==it);
 }
};

void out(int*data){
for(int i=0;i<10;i++){
 for(int j=0;j<10;j++)
 cout<<data[j+i*10];
cout<<endl;
}
}

int main(){