21.3 – Обзор итераторов STL

Итератор – это объект, который может перемещаться по контейнерному классу (перебирать его элементы), при этом пользователю не нужно знать, как реализован этот контейнер. Для многих классов (особенно списков и ассоциативных классов) итераторы являются основным способом доступа к элементам.

Итератор лучше всего представить себе как указатель на заданный элемент в контейнере с набором перегруженных операторов для предоставления набора четко определенных функций:

• operator* – разыменование итератора возвращает элемент, на который итератор в данный момент указывает;
• operator++ – перемещает итератор к следующему элементу в контейнере. Большинство итераторов также предоставляют operator-- для перехода к предыдущему элементу;
• operator== и operator!= – базовые операторы сравнения, чтобы определить, указывают ли два итератора на один и тот же элемент. Чтобы сравнить значения, на которые указывают два итератора, сначала разыменуйте эти итераторы, а затем используйте оператор сравнения;
• operator= – присваивание итератору новой позиции (обычно в начало или в конец элементов контейнера). Чтобы присвоить значение элемента, на который указывает итератор, сначала разыменуйте этот итератор, а затем используйте оператор присваивания.

Каждый контейнер включает четыре основные функции-члена для использования с operator=:

• begin() возвращает итератор, представляющий начало элементов в контейнере;
• end() возвращает итератор, представляющий элемент сразу за концом элементов;
• cbegin() возвращает константный (только для чтения) итератор, представляющий начало элементов в контейнере;
• cend() возвращает константный (только для чтения) итератор, представляющий элемент сразу за концом элементов.

Может показаться странным, что end() не указывает на последний элемент в списке, но это сделано в первую очередь для упрощения циклов: итерация по элементам может продолжаться до тех пор, пока итератор не достигнет end(), и тогда вы знаете, что перебрали все элементы контейнера.

Наконец, все контейнеры предоставляют (как минимум) два типа итераторов:

• container::iterator предоставляет итератор для чтения/записи;
• container::const_iterator предоставляет итератор только для чтения.

Давайте посмотрим на несколько примеров использования итераторов.

Итерация по контейнеру vector

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vect;
    for (int count=0; count < 6; ++count)
        vect.push_back(count);

    std::vector<int>::const_iterator it; // объявляем итератор только для чтения
    it = vect.cbegin();                  // присваиваем ему начало вектора
    while (it != vect.cend())    // пока it не достигнет до конца
        {
        std::cout << *it << " "; // выводим значение элемента, на который указывает it
        ++it;                    // и переходим к следующему элементу
        }

    std::cout << '\n';
}

Этот напечатает следующее:

0 1 2 3 4 5

Итерация по контейнеру list

А теперь сделаем то же самое со списком:

#include <iostream>
#include <list>

int main()
{

    std::list<int> li;
    for (int count=0; count < 6; ++count)
        li.push_back(count);

    std::list<int>::const_iterator it; // объявляем итератор
    it = li.cbegin();                  // присваиваем ему начало списка
    while (it != li.cend())      // пока it не достигнет до конца
    {
        std::cout << *it << " "; // выводим значение элемента, на который указывает it
        ++it;                    // и переходим к следующему элементу
    }

    std::cout << '\n';
}

Этот код печатает:

0 1 2 3 4 5

Обратите внимание, что код почти идентичен случаю с вектором, хотя векторы и списки внутри имеют почти совершенно разные реализации!

Итерация по контейнеру set

В следующем примере мы собираемся создать набор из 6 чисел и использовать итератор для печати значений в этом наборе:

#include <iostream>
#include <set>

int main()
{
    std::set<int> myset;
    myset.insert(7);
    myset.insert(2);
    myset.insert(-6);
    myset.insert(8);
    myset.insert(1);
    myset.insert(-4);

    std::set<int>::const_iterator it; // объявляем итератор
    it = myset.cbegin();              // присваиваем ему начало набора
    while (it != myset.cend())   // пока it не достигнет до конца
    {
        std::cout << *it << " "; // выводим значение элемента, на который указывает it
        ++it;                    // и переходим к следующему элементу
    }

    std::cout << '\n';
}

Эта программа дает следующий результат:

-6 -4 1 2 7 8

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

Итерация по контейнеру map

Это немного сложнее. map и multimap принимают пары элементов (определяемые как std::pair). Чтобы было проще создавать пары, мы используем вспомогательную функцию make_pair(). std::pair позволяет получить доступ к элементам пары через члены first (первый) и second (второй). В нашем контейнере map мы используем первый элемент пары как ключ, а второй – как значение.

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<int, std::string> mymap;
    mymap.insert(std::make_pair(4, "apple"));
    mymap.insert(std::make_pair(2, "orange"));
    mymap.insert(std::make_pair(1, "banana"));
    mymap.insert(std::make_pair(3, "grapes"));
    mymap.insert(std::make_pair(6, "mango"));
    mymap.insert(std::make_pair(5, "peach"));

    // объявляем константный итератор и присваиваем ему начало контейнера map
    auto it{ mymap.cbegin() }; 
    while (it != mymap.cend()) // пока it не достигнет конца
    {
        // выводим значение элемента, на который указывает it
        std::cout << it->first << "=" << it->second << " ";
        ++it;            // и переходим к следующему элементу
    }

    std::cout << '\n';
}

Эта программа дает следующий результат:

1=banana 2=orange 3=grapes 4=apple 5=peach 6=mango

Обратите внимание на то, насколько легко итераторы позволяют проходиться по всем элементам контейнера. Вам совершенно не нужно заботиться о том, как map хранит свои данные!

Заключение

Итераторы предоставляют простой способ перебрать элементы контейнерного класса без необходимости понимать, как реализован этот контейнерный класс. В сочетании с алгоритмами STL и функциями-членами контейнерных классов итераторы становятся еще мощнее. В следующем уроке вы увидите пример использования итератора для вставки элементов в список (который не предоставляет перегруженный operator[] для прямого доступа к своим элементам).

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

Теги