11 Мар 2023

Итераторы

11 Мар 2023

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

Итератор – легковесный объект, который хранит только указатель на тип объектов контейнера и определяется 5 шаблонными параметрами, два из которых являются обязательными: категория итератора и тип значения, которое может быть получено путем разыменовывания итератора. Для каждой категории итератора перегружены операции префиксного и постфиксного инкрементов (++), сравнения (==, !=) и разыменования (*). После выполнения оператора ++ итератор будет указывать на следующий в коллекции элемент, если он существует. Операторы == и != вернут true или false в зависимости от того, указывают ли итераторы на один и тот же объект. Как и при работе с указателями, для получения объекта используется операция разыменования. Также как для указателей, для них применимы операции разыменования (*,->), инкремента (++) и сравнения (==, !=).

Для каждого типа контейнера существуют свои итераторы. Это связано с особенностями расположения элементов в памяти и доступа к ним. Итераторы делятся на следующие категории:

ввода (InputIterator);
однонаправленные (ForwardIterator);
двунаправленные (BidirectionalIterator);
произвольного доступа (RandomAccessIterator);
непрерывные (ContiguousIterator, начиная с C++17);
вывода (OutputIterator).

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

it, it1, it2 – итераторы;
a – поле или метод базового типа, на который указывает итератор;
n – число элементов или индекс.

Ячейка со значением ± означает, что операция выполнима только если итератор не является константным.

В зависимости от категории итераторов, их можно использовать в разных стандартных алгоритмах. Так, например, алгоритм подсчета числа элементов (std::count) применим ко всем типам итераторов, кроме итераторов вывода, а алгоритм сортировки (std::sort) только к итераторам произвольного доступа и непрерывным итераторам.

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

#include <vector>
#include <deque>
#include <forward_list>
#include <set>
#include <string>
#include <iostream>

template <typename InputIt, typename T>
constexpr T sum(InputIt first, InputIt last, T init)
{
  while (first != last)
  {
    init = std::move(init) + *first;
    ++first;
  }

  return init;
}

int main()
{
  std::forward_list<int> flist { 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 };
  std::deque<int>        deque { 1, 1, 2, 3, 5, 8, 13 };
  std::vector<float>    vector { 0.3, 0.5 ,0.7 ,0.9 ,1.1 };
  std::set<std::string>    set { "One", "Two", "Three", "Four" };

  auto  flist_sum = sum(flist.begin(), flist.end(), 0);
  auto  deque_sum = sum(deque.begin(),  deque.end(), 0);
  auto vector_sum = sum(vector.begin(), vector.end(), 0.0f);
  auto    set_sum = sum(set.begin(), set.end(), std::string {});

  std::cout << " flist_sum = " << flist_sum  << "\n";
  std::cout << " deque_sum = " << deque_sum  << "\n";
  std::cout << "vector_sum = " << vector_sum << "\n";
  std::cout << "   set_sum = " << set_sum    << std::endl;


  // flist_sum = 7
  // deque_sum = 33
  // vector_sum = 3.5
  // set_sum = FourOneThreeTwo

  return 0;
}

Для подсчета суммы используется шаблон функции, принимающей два итератора и начальное значение. Функция использует такие операции над итераторами, как сравнение (!=), разыменование для чтения (*) и префиксный инкремент (++). Эти операции выполнимы для всех категорий, начиная с InputIterator (кроме OutputIterator). Эта категория самая низкая из пяти, поэтому функция может работать со всеми пятью категориями итераторов. Для определения типа возвращаемого значения используется третий аргумент функции.

Для того, чтобы получить итератор на начало и конец последовательности элементов, у любого контейнера существуют методы begin и end. Контейнер forward_list использует однонаправленные итераторы, deque и set – двунаправленные, а vector – итераторы произвольного доступа. Вызов функций для разных контейнеров приводит к инстанцированию шаблона с соответствующим типом итератора и типом хранимого значения.

Итераторам одного типа нельзя присвоить значение итераторов другого типа, за исключением константного итератора, который может принять значение точно такого же, но не константного.

Для более удобной работы с итераторами существуют операции:

std::distance – возвращает расстояние (число переходов) между двумя итераторами;
std::advance – модифицирует переданный итератор, сдвигая его на n позиций вперед или назад. Сдвиг на положительное число доступен для любых типов итераторов. Сдвиг на отрицательное число доступен для итераторов, начиная с категории BidirectionalIterator;
std::prev – возвращает n-ый по счету предыдущий итератор;
std::next – возвращает n-ый по счету следующий итератор.

Для изменения поведения итератора или добавления дополнительного функционала, используются итераторы-адаптеры. Например, адаптер reverse_iterator позволяет обходить контейнер в обратном направлении, а back_insert_iterator вставлять элементы в конец контейнера.

Итераторы часто упрощают программирование, однако их неправильное использование не всегда отслеживается компилятором и может приводить к ошибкам. Например, можно сравнить итераторы от разных контейнеров (V662) или разыменовать невалидный итератор (V783). PVS-Studio позволяет детектировать эти и некоторые другие паттерны ошибок связанные с итераторами с помощью диагностик V803, V789 и V738.