Лекция 18

Мощь STL заключается в том, что алгоритмы ничего не знают про контейнеры, а контейнеры ничего не знают про алгоритмы. Для того, чтобы склеить контейнеры и алгоритмы в STL существуют итераторы.

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

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

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

Рассмотрим использование итератора на примере массива:

int a = {41, 42, 43};
int b[3];
copy(a, a + 3, b);

Если a и b объявлены в одном кадре стека, то правильнее написать так:

int a = {41, 42, 43};
int b[sizeof(a)/sizeof(*a)];
copy(a, a + sizeof(a)/sizeof(*a), b);

А так итератор применяют со стандартным контейнером:

vector<int> v1{1, 2, 3}, v2(3);
copy(v1.begin(), v1.end(), v2.begin());

Здесь begin() это итератор на первый элемент, а end() итератор на "элемент", следующий за последним.

Итераторы в C++11

В С++11 работа с итераторами изменилась,теперь она осуществляется следующим образом:

std::copy(begin(a), end(a), begin(v));

Пример функции печати каждого элемента контейнера:

void print(Cont const & c)
{
    for(auto it = begin(c), e = end(c); it != e; ++it)
        std::cout << *it << ' ';
    std::cout <<std::entl;
}

На самом деле эта функция нарушает философию STL так как в функцию передается контейнер, а не итераторы.

Рассмотрим использование print

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

Здесь функция print нормально отработает для вектора, но для массива она не должна сработать, так как у массива нет begin() и end(). Однако для массива сработает следующая специализация шаблона:

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

Если имеется библиотечный тип myvector такой, что выполнены два условия:

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

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

Концепты

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

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

Вложенные типы

Внутри структуры или класса можно описывать вложенные типы, как через typedef, так и через описание других классов. Для доступа к таким типам вне класса, к имени типа добавляется имя вложенного типа и два двоеточия:

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

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

Второй случай использования `typename`

в 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, а вложенный тип. Это второй вариант использования этого ключевого слова.

Вложенный класс

А так вложенный тип описывается с помощью другого класса:

class myvector {
    template<typename T>
    class myvector_it {
        T* cur;
    public:
        myvector_it(T* cur): cur(cur) {}
        friend bool operator != (...) {...}
        void operator++() { ++cur; }
        T& operator*() {return *cur}
    }
myvector_it begin() {return myvector_it(data);}
myvector_it end() {return myvector_it(data + size);}
}