10.24 – Знакомство с итераторами

Итерации по массиву (или другой структуре) данных – довольно обычное дело в программировании. И до сих пор мы рассмотрели много разных способов сделать это: с помощью циклов и индексов (циклы for и while), с указателями и арифметикой указателей, а также с циклами for на основе диапазона (for-each):

#include <array>
#include <cstddef>
#include <iostream>
 
int main()
{
  // Тип автоматически выводится как std::array<int, 7> (требуется C++17).
  // Используйте тип std::array<int, 7>, если ваш компилятор не поддерживает C++17.
  std::array data{ 0, 1, 2, 3, 4, 5, 6 };
  std::size_t length{ std::size(data) };
 
  // цикл while с явным индексом
  std::size_t index{ 0 };
  while (index != length)
  {
    std::cout << data[index] << ' ';
    ++index;
  }
  std::cout << '\n';
 
  // цикл for с явным индексом
  for (index = 0; index < length; ++index)
  {
    std::cout << data[index] << ' ';
  }
  std::cout << '\n';
 
  // цикл for с указателем (Примечание: ptr не может быть const, потому что мы увеличиваем его)
  for (auto ptr{ &data[0] }; ptr != (&data[0] + length); ++ptr)
  {
    std::cout << *ptr << ' ';
  }
  std::cout << '\n';
 
  // цикл for на основе диапазона
  for (int i : data)
  {
    std::cout << i << ' ';
  }
  std::cout << '\n';
 
  return 0;
}

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

Цикл с указателями и арифметикой указателей является многословным и может сбивать с толку читателей, не знакомых с правилами арифметики указателей. Арифметика указателей также работает только в том случае, если элементы расположены в памяти последовательно (что верно для массивов, но не верно для других типов контейнеров, таких как списки, деревья и карты).

Циклы for на основе диапазона немного интереснее, поскольку механизм итерации по нашему контейнеру скрыт – и еще, они работают для всех видов различных структур (массивов, списков, деревьев, карт и т.д.). Как это работает? Они используют итераторы.

Итераторы

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

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

Как только соответствующий тип итератора создан, программист может затем использовать интерфейс, предоставляемый этим итератором, для обхода и доступа к элементам, не беспокоясь о том, какой вид обхода выполняется, или как данные хранятся в контейнере. И поскольку итераторы C++ обычно используют один и тот же интерфейс для обхода (operator++ для перехода к следующему элементу) и доступа (operator* для доступа к текущему элементу), мы можем выполнять итерацию по большому количеству различных типов контейнеров, используя совместимый метод.

Указатели как итератор

Самый простой вид итератора – это указатель, который (с использованием арифметики указателей) работает с данными, хранящимися в памяти последовательно. Давайте вернемся к простому обходу массива с использованием указателя и арифметики указателя:

#include <array>
#include <iostream>
 
int main()
{
  std::array data{ 0, 1, 2, 3, 4, 5, 6 };
 
  auto begin{ &data[0] };
  // обратите внимание, что это указывает на одно место за последним элементом
  auto end{ begin + std::size(data) };
 
  // цикл for с указателем
  for (auto ptr{ begin }; ptr != end; ++ptr) // ++ для перехода к следующему элементу
  {
    std::cout << *ptr << ' '; // Косвенное обращение для получения значения текущего элемента
  }
  std::cout << '\n';
 
  return 0;
}

Вывод программы:

0 1 2 3 4 5 6

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

Затем указатель выполняет итерацию между begin и end, и к текущему элементу можно получить доступ путем косвенного обращения через указатель.

int* end{ &array[std::size(array)] };

int* end{ array.data() + std::size(array) }; // data() возвращает указатель на первый элемент

Итераторы стандартной библиотеки

Итерация – настолько распространенная операция, что все контейнеры стандартной библиотеки предлагают прямую поддержку итерации. Вместо того чтобы вычислять наши начальные и конечные точки самостоятельно, мы можем просто запросить у контейнера начальную и конечную точки с помощью функций с удобными названиями begin() и end():

#include <array>
#include <iostream>
 
int main()
{
  std::array array{ 1, 2, 3 };
 
  // запрашиваем у нашего массива начальную и конечную точки
  // (через функции-члены begin и end).
  auto begin{ array.begin() };
  auto end{ array.end() };
 
  for (auto p{ begin }; p != end; ++p) // ++ для перехода к следующему элементу.
  {
    std::cout << *p << ' '; // Косвенное обращение к получению значения текущего элемента.
  }
  std::cout << '\n';
 
  return 0;
}

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

1 2 3

Заголовок <iterator> также содержит две общие функции (std::begin и std::end), которые тоже можно использовать:

#include <array>
#include <iostream>
#include <iterator> // для std::begin и std::end
 
int main()
{
  std::array array{ 1, 2, 3 };
 
  // Использовать std::begin and std::end, чтобы получить начальную и конечную точки
  auto begin{ std::begin(array) };
  auto end{ std::end(array) };
 
  for (auto p{ begin }; p != end; ++p) // ++ для перехода к следующему элементу
  {
    std::cout << *p << ' '; // Косвенное обращение для получения значения текущего элемента
  }
  std::cout << '\n';
 
  return 0;
}

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

1 2 3

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

Возвращаемся к циклам на основе диапазона

Все типы, которые имеют функции-члены begin и end или могут использоваться с std::begin и std::end, могут использоваться в циклах for на основе диапазона.

#include <array>
#include <iostream>
 
int main()
{
  std::array array{ 1, 2, 3 };
 
  // Это делает то же самое, что и цикл, который мы использовали раньше
  for (int i : array)
  {
    std::cout << i << ' ';
  }
  std::cout << '\n';
 
  return 0;
}

За кулисами цикл for на основе диапазона вызывает begin() и end() того типа, который нужно перебрать. std::array имеет функции-члены begin и end, поэтому мы можем использовать его в цикле на основе диапазона. Фиксированные массивы в стиле C могут использоваться с функциями std::begin и std::end, поэтому мы также можем перебирать их с помощью цикла на основе диапазона. Однако с динамическими массивами это не работает, потому что для них нет функции std::end (поскольку информация о типе не содержит длину массива).

Позже вы узнаете, как добавлять функции к вашим типам, чтобы их можно было использовать и с циклами for на основе диапазона.

Циклы for на основе диапазона – не единственное, что использует итераторы. Они также используются в std::sort и других алгоритмах. Теперь, когда вы знаете, что это такое, вы заметите, что они довольно часто используются в стандартной библиотеке.

Недействительность итератора (висячие итераторы)

Подобно указателям и ссылкам, итераторы могут оставаться «висячими», если перебираемые по адресу элементы изменились, или были уничтожены. Когда это происходит, мы говорим, что итератор недействителен. Доступ к недействительному итератору приводит к неопределенному поведению.

Некоторые операции, которые изменяют контейнеры (например, добавление элемента в std::vector), могут иметь побочный эффект, заставляя элементы в контейнере изменять адреса. Когда это происходит, существующие итераторы для этих элементов станут недействительными. Хорошая справочная документация C++ должна указывать, какие операции с контейнером могут или сделают итераторы недействительными. В качестве примера смотрите раздел «Iterator invalidation» в std::vector на cppreference.

Вот пример этого:

#include <iostream>
#include <vector>
 
int main()
{
	std::vector v { 1, 2, 3, 4, 5, 6, 7 };
 
	auto it { v.begin() };
 
	++it; // переходим ко второму элементу
	std::cout << *it << '\n'; // ok: напечатает 2
 
	v.erase(it); // стираем элемент, по которому в данный момент выполняется итерация
 
	// erase() делает недействительными итераторы для стертого элемента
    // (и последующих элементов),  поэтому итератор "it" теперь недействителен
	
	++it; // неопределенное поведение
	std::cout << *it << '\n'; // неопределенное поведение
	   
	return 0;
}

Теги