Итераторы

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

Существуют несколько видов итераторов. Они образуют иерархию, отличаются друг от друга наличием (отсутствием) некоторых свойств:

Итератор ввода ← Последовательный итератор ← Двунаправленный итератор ← Итератор произвольного доступа Итератор вывода ←

На схеме сверху показаны связи между итераторами. Эти связи означают, например, что последовательный итератор обладает всеми свойствами итераторов ввода и вывода, поэтому он может их заменять.

Замечание Здесь и далее по тексту приняты следующие обозначения: 

Х - некторый класс (контейнер);
IT - класс итератора
u, a, b - объекты класса X;
r - итератор;
T - значимый тип (тип элементов контейнера);
t - значение типа T; n - целочисленное значение.

Итераторы ввода

Итераторы ввода (Input iterators) позволяют изменять значения объектов контейнера. Требования к итераторам ввода представлены в листинге input_iterator.h.

input_iterator.h

template<class TYPE>
class input_iterator {
    TYPE* element;
public:
    input_iterator(input_iterator<TYPE> iit){
        element = iit.element;
    }
    ~input_iterator(){}
    
    input_iterator<TYPE> operator = (const input_iterator<TYPE>& iit){
        element = iit.element;
        return *this;
    }
    TYPE operator *() const{
        return *element;
    }
    virtual input_iterator<TYPE> operator ++() = 0;
    virtual input_iterator<TYPE> operator ++(int) = 0;
    
    bool operator == (const input_iterator<TYPE>& iit) const{
        return element == iit.element;
    }
};

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

Итераторы вывода

Итераторы вывода (output iterators) позволяют получать значения элементов контейнера. Требования к итераторам вывода представлены в листинге output_iterator.h.

output_iterator.h

template<class TYPE>
class output_iterator {
    TYPE* element;
public:
    output_iterator(output_iterator<TYPE> oit): element(oit.element){}
    ~output_iterator(){}
    
    TYPE& operator *() { return *element; }
    virtual output_iterator<TYPE> operator ++() = 0;
    virtual output_iterator<TYPE> operator ++(int) = 0;
    
    bool operator == (const output_iterator<TYPE>& iit) const{
        return element == iit.element;
    }
};

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

Consecutive iterators

Таблица 3 Требования последовательного итератора

выражение	возвращаемый тип	утверждение/примечание состояние до/после
IT u;		примечание: u может иметь исключительное значение. примечание: предполагается деструктор.
IT()		примечание: IT() может быть исключительным.
IT(a);		a == IT(a)
IT u(a); IT u = a;		после: u == a.
a == b	обратимый в bool	== - это отношение эквивалентности.
a != b	обратимый в bool
r = a	IT&	после: r == a.
*a	обратимый в T	до: a - разыменовываемое. a == b подразумевает *a == *b. Если IT - модифицируемый, то *a = t - допустимо.
++r	IT&	до: r - разыменовываемое. после: r - разыменовываемое или r - законечное. r == s и r - разыменовываемое подразумевает ++r == ++s. &r == &++r.
r++	IT

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

bidirectional iterators

Таблица 4 Требования двунаправленного итератора (в дополнение к последовательному итератору)

выражение	возвращаемый тип	утверждение/примечание состояние до/после
--r	IT&	до: существует s такое, что r == ++s. после: s - разыменовываемое. --(++r) == r. --r == --s подразумевает r == s. &r == &--r.
r--	IT

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

Random access iterators

Таблица 5 Требования итератора произвольного доступа (в дополнение к двунаправленному итератору)

выражение	возвращаемый тип	утверждение/примечание состояние до/после
r += n	IT&
a + n n + a	IT	a + n == n + a.
r -= n	IT&
a - n	IT
b - a	Distance	до: существует значение n типа Distance такое, что a + n = b. b == a + (b - a).
a[n]	обратимый в T
a < b	обратимый в bool	< - это отношение полного упорядочения
a > b	обратимый в bool	> - это отношение полного упорядочения, противоположное <.
a >= b	обратимый в bool
a <= b	обратимый в bool