Примерный план лекции 18 по курсу CS211 (ФИИТ Мехмат ЮФУ) / рассказано не всё

cs211-lecture-18

## Роль итераторов стандартной библиотеки

Напомним код алгоритма `copy`

    template<typename ItIn, typename ItOut>
    void copy(ItIn b, ItIn e, ItOut b1)
    {
        while (b != e) {
            *b1 = *b;
            ++b;
            ++b1;
        }
    }

**Итератор** это любой тип, к которому применимы операции:

* продвижение: `++`, 
* обращение к элементу, на который указывает итератор: `*`,
* проверка неравенства: `!=`. 

**Замечание.** В зависимости от дополнительных операций (например, `--`) и дополнительной 
семантики операций (например, пройтись по последовательности можно только один раз)
выделяют разные _категории итераторов_, они будут рассмотрены существенно позже.

### Откуда брать итераторы?

Все указатели (тип `T *`) являются итераторами. Все основные стандартные контейнеры 
имеют функции-члены `begin` и `end`. 

**Пример 1.**

    int a[] = {41, 42, 43};
    std::vector<int> v(3);
    std::copy(a, a + 3, v.begin());
    
**Пример 2.**

    int b[3];
    std::copy(v.begin(), v.end(), b);
    
Смысл `end` для контейнера стандартной библиотеки:

> итератор на «элемент», следующий за последним.

### C++11: std::begin и std::end

Кроме того, в C++11 для пущей обобщённости введены две свободные функции
`begin` и `end`, которые определны для любого стандартного контейнера `c`, у 
которого есть `c.begin()` и `c.end()` и просто вызывают эти функции. Кроме того,
они определены для массивов (но не указателей!). То есть предыдущий пример можно 
переписать следующим образом.

    std::copy(begin(a), end(a), begin(v));
    
Это делает код более универсальным. Напишем, к примеру функцию печати каждого элемента:

    template <typename Cont>
    void print(Cont const & c)
    {
        for (auto it = begin(c), e = end(c); it != e; ++it)
            std::cout << *it << ' ';
        std::cout << std::endl;
    }
    
Такую функцию можно использовать и для вектора, и для обычного массива:

    std::vector<int> v {1 , 2, 3};
    int a[] = {4, 5, 6};
    print(v);
    print(a);

Работает благодаря наличию _специализации шаблона_:

    template <class T, size_t N>
    T* end (T(&arr)[N]);

Более того, если имеется библиотечный тип `myvector`, который:

1. Не имеет функций-членов `begin`, `end`.
2. Мы не можем менять (добавить в него `begin` / `end`).

Тогда мы можем написать собственные версии свободных `begin`/`end` для этого
типа и `print` станет работать и с ним.

## Ограничения на типы-параметры и вложенные ()синонимы) типов

При параметрическом (_обобщённом_, generic) программировании в C++ на 
параметры-типы нет явных ограничений. Однако, если рассмотреть код любого 
алгоритма, то о таких ограничениях можно догадаться. Набор ограничений для
параметра-типа в C++ называется _концептом_ (concept). Концепты исторически
являлись частью документации. В последние примерно 10 лет их стремятся вынести 
на уровень языка.

Примеры концептов из книги Страуструпа

* `Assignable<X,Y>`
* `Predicate<F,X>`,
* `Streamable<X>`.

Для общего итератора нет единого концепта. Вместо этого есть пять концептов для
специальных итераторов. Например, для итератора `std::vector` концепт называется
`Random_access_iterator<X>`.

### Двухфазная компиляция шаблонов

Из сказанного следует, что полная информация о типах и, соответственно,
проверка кода шаблона возможна только в **точке инстанцирования**. То есть
когда мы в «основной программе» пишем

    vector<Student> v { /* init... */ }
    print(v); // Error: no operator<< for Student

### Тип возвращаемого значения `begin`/`end`

Поскольку про типы неизвестно почти ничего, регулярно возникает проблема
нехватки информации. Например, без использования `auto` непонятно, как написать
цикл из `print`. В стандартной библиотеке это решается введением вложенных
синонимов типов (`typedef`). Например, заведём итератор от списка:

    std::list<int> l {1, 2, 3};
    std::list<int>::iterator it = l.begin();

Если мы получили векторк, список или другой контейнер стандартной библиотеки
в функцию по `const &`, то обычный итератор не подойдёт:

    void f(std::list<int> const & l)
    {
        std::list<int>::const_iterator it = l.begin();
    }

в C++98 цикл из print выглядел бы так:

    template <typename Cont>
    void print(Cont const & c)
    {
        for (typename c::const_iterator = c.begin(), e = c.end(); it != e; ++it)
            std::cout << *it << ' ';
        std::cout << std::endl;
    }

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

### Диапазонный `for` из C++11

Программисты много лет страдали от всех этих `typename`, `::iterator`, `begin` и 
`end` и потому в C++11 добавили новый `for` и `auto`:

    template <typename Cont>
    void print(Cont const & c)
    {
        for (auto const & x : c)
            std::cout << x << ' ';
        std::cout << std::endl;
    }

## Реализация простейшего итератора

    template <typename T>
    class myvector_iterator {

        T * current;

    public:
        myvector_iterator(T * current): current(current) {}

        myvector_iterator& operator++() {/* ... */}
        
        T&                 operator*()  {/* ... */}
        
        template<typename S>
        friend
        bool               operator!=(myvector_iterator<S> it1, 
                                      myvector_iterator<S> it2)
                                      { return it1.current != it2.current; }
    };

Теперь в наш вектор можно добавить функции-члены `begin`/`end` или перегрузить
внешние функции:

### Вариант 1 для `begin`/`end`

    template<typename T>
    class myvector {
    
        // ...
        
        myvector_iterator<T> begin() { return data; } // implicit constructor

        myvector_iterator<T> end()   { return data + size; }
    
    };

### Вариант 2 для `begin`/`end`

    template <typename T>
    myvector_iterator<T> begin(myvector<T> /* const */ & myv)
    {
        return &myv[0]; 
    }

    template <typename T>
    myvector_iterator<T> end(myvector<T> /* const */ & myv)
    {
        return &myv[myv.size() - 1]; 
    }

### Итератор для алгоритмов стандартной библиотеки

Если хотим, чтобы наш итератор работал с алгоритмами стандартной библиотеки, то
следует добавить в него 5 определений типов:

* iterator_category
* value_type
* difference_type
* pointer
* reference

Самое нетривиальное из них — первое. Категории итераторов определяют, что можно 
делать с итератором и какова семантика этих действий. Стандартных категорий пять. 
Эти типы можно определить унаследовавшись от стандартного типа
`std::iterator` с пятью шаблонными параметрами соответственно. Причём необходимо
указать лишь первые два, а остальные имеют значнеия по умолчанию:

    template <typename T>
    class myvector_iterator: public std::iterator<std::forward_iterator_tag, T> // ...