> For the complete documentation index, see [llms.txt](https://sweethome.gitbook.io/advanced-cpp/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sweethome.gitbook.io/advanced-cpp/standard_library/iterators.md).

# Итераторы

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

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

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

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

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

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

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

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

{% code title="input\_iterator.h" %}

```cpp
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;
    }
};
```

{% endcode %}

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

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

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

{% code title="output\_iterator.h" %}

```cpp
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;
    }
};
```

{% endcode %}

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

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 |                                                                                 |