Итераторы

Итератор — это объект, который позволяет перебирать элементы в контейнере и предоставлять доступ к отдельным элементам. Итераторы обеспечивают абстракцию, позволяющую работать с контейнерами универсальным образом, не завися от их конкретной реализации.

std::string s = "123";
std::string::iterator s_it = s.begin();

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

std::vector<int> v = {1, 2, 3};
std::vector<int>::iterator v_it = v.begin();

Виды итераторов

Есть разделение по двум категориям:

• прямой и обратный — указывает порядок прохода по элементам; например для обратного итератора операция инкремента смещает оператор в ближе к началу
• изменяемый и константный — разрешает или запрещает изменять элементы, на которые указывает итератор

Интерфейс

Использование итераторов очень похоже на использование указатей.

Разыменование

• operator* — возвращает ссылку на текущий элемент, на который указывает итератор
• operator-> — позволяет использовать итератор, как если бы он был указателем на объект

struct Point { float x; float y; };
std::vector<Point> v = {{0, 0}, {1, 1}};

auto it = v.rbegin();
*it = {0, 2};
it->x = 2;

Инкремент и декремент:

• operator++ — перемещает итератор на следующий элемент; префиксный инкремент возвращает измененный итератор, а постфиксный возвращает копию итератора перед изменением
• operator-- — перемещает итератор на предыдущий элемент; префиксный возвращает измененный итератор, а постфиксный возвращает копию итератора перед изменением

int i;
std::vector<int> v = {1, 2, 3};

auto it = v.begin();
++it;
i = *it; // i == 2
--it;
i = *it; // i == 1

примечание

Если возвращаемое значение игнорируется, следует использовать префиксную запись (++it вместо it++), т.к. она не создаёт копии.

Переход к произвольному элементу:

• operator+ и operator- — возвращают новый итератор, смещённый на указанное количество позиций
• operator+= и operator-= — смещают итератор на указанное количество позиций

int i;
std::vector<int> v = {1, 2, 3};

auto it = v.cbegin();
it += 2;
i = *it;       // i == 3
i = *(it - 2); // i == 1

Выражение *(it - 2), как и для указателя, может быть записано как it[-2].

Сравнение:

• operator== — возвращает true, если интераторы указывают на один и тот же элемент
• operator!= — возвращает true, если интераторы указывают на разные элементы

STL

Большинство контейнеров стандартной библиотеки предоставляют итераторы для навигации по своим элементам и имеют одинаковый интерфейс:

• итераторы: begin и end
• константные итераторы: cbegin и cend
• обратные интераторы: rbegin и rend
• константные обратные итераторы: crbegin и crend

Здесь "c" означает "const", а "r" — "reverse".

std::list<int> l = {1, 2, 3};

// iterator
l.begin(); l.end();

// const iterator
l.cbegin(); l.cend();

// reverse iterator
l.rbegin(); l.rend();

// const reverse iterator
l.crbegin(); l.crend();

Методы вида begin указывают на первый (с учётом направления) элемент в контейнере, а end — на элемент, "следующий за последним". Это нужно для организации цикла.

for (auto it = l.begin(); it != l.end(); ++it) {
  // forward direction
}

for (auto rit = l.rbegin(); rit != l.rend(); ++rit) {
  // backward direction
}

Класс итератора сам по себе, без использования этих методов, доступен через *::iterator; например для контейнера std::map<int, int> класс итератора доступен как std::map<int, int>::iterator.

Range-base loop

Запись вида

for (auto it = container.begin(); it != container.end(); ++it) {
  auto& element = *it;
  // some actions with the element
}

может быть упрощена до вида

for (auto& element : container) {
  // some actions with the element
}

и называется range-based loop.