Рубрики
Программирование

STL: Итераторы

Введение

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

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

Содержание:

Основные операции над итераторами

Рассмотрим операции, поддерживаемые итераторами:

  • разыменование (*it) — получение доступа к элементу, на который указывает итератор;
  • доступ к членам элемента (it->member) — получение доступа к полю или методу элемента, на который указывает итератор;
  • инкремент (++it, it++) — перемещение итератора к следующему элементу;
  • декремент (--it, it--) — перемещение итератора к предыдущему элементу;
  • сравнение (it1 == it2, it1 != it2) — проверка на одинаковость/разность элементов, на которые указывает итератор;
  • арифметические операции:
    • сдвига (it + n, it - n) — возвращает итератор, который смещен от итератора it на n позиций,
    • перемещения (it += n, it -= n) — перемещает итератор it на n позиций,
    • индексации (it[n]) — возвращает элемент, смещенный относительно it на n позиций;
  • вычисление расстояния между итераторами (it1 - it2) — возвращает количество позиций между двумя итераторами;
  • сравнение порядка (<, >, <=, =>) — сравнение положения элементов, на которые указывают два итератора, друг относительно друга.

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

Как уже говорилось во введении, доступные операции зависят от категории итератора.

Пример использования операторов представлен в разделе работа с итераторами.

Категории итераторов

Итераторы однократного доступа

Входные итераторы (итераторы ввода, input iterators) — предназначены для однократного чтения данных из последовательности (только последовательное движение вперед, каждый элемент может быть прочитан один раз). Используются в потоковых итераторах для чтения (std::istream_iterator).

Поддерживают:

  • разыменование для чтения,
  • инкремент,
  • сравнение на равенство/неравенство.

Выходные итераторы (output iterators) — предназначены для однократной записи данных в последовательности (только последовательное движение вперед, каждый элемент может быть записан один раз). Используются в потоковых итераторах для записи (std::ostream_iterator).

Поддерживают:

  • разыменование для записи,
  • инкремент,
  • сравнение на равенство/неравенство.

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

Итераторы многократного доступа

Однонаправленные итераторы (forward iterators) — объединяют возможности входных и выходных итераторов, позволяя многократно читать и записывать данные, а так же проходить по последовательности несколько раз. Используются в std::forward_list, std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap.

Поддерживают:

  • разыменование для чтения/записи,
  • инкремент,
  • сравнение на равенство/неравенство.

Двунаправленные итераторы — расширяют однонаправленные итераторы, добавляя возможность движения в обратном направлении. Используются в std::list, std::set, std::multiset, std::map, std::multimap.

Поддерживают:

  • разыменование для чтения/записи,
  • инкремент,
  • декремент,
  • сравнение на равенство/неравенство.

Итераторы произвольного доступа (random access iterator) — предоставляют наиболее полную функциональность, позволяя перемещаться на произвольное количество элементов за константное время. Используются в std::vector, std::deque, std::array, std::string.

Поддерживают:

  • разыменование для чтения/записи,
  • инкремент,
  • декремент,
  • сравнение на равенство/неравенство,
  • арифметические операции,
  • сравнение порядка.

Смежные итераторы C++20 (contiguous iterators) — итераторы произвольного доступа, которые гарантируют, что элементы расположены в памяти непрерывно. Используются в std::vector, std::array, std::string, std::span.

В libstdc++ (реализации стандартной библиотеки GCC) итераторы контейнеров с непрерывным размещением элементов могут быть представлены:

  • обычным указателем для std::array;
  • шаблонным __gnu_cxx::__normal_iterator, который является оберткой над указателем (для std::vector, std::string, std::span) — данный класс-обертка обеспечивает дополнительный контроль над итераторами.

Примечание: методы класса __normal_iterator могут быть оптимизированы компилятором до простой работы с указателями.

Использование __normal_iterator позволяет контролировать типы контейнеров и избежать «смешивания».
Пример получаемой ошибки:

#include <string>
#include <vector>
#include <algorithm>

void conversion_error()
{
    std::vector<char>::iterator v_i; // Итератор динамического массива char
    std::string::iterator s_i; // Итератор строки

    std::swap(v_i, s_i); // Ошибка компиляции: нет соответствующей функции для вызова «swap(std::vector<char>::iterator&, std::__cxx11::basic_string<char>::iterator&)»
}

Также __normal_iterator обеспечивает ограничения полиморфмизма итераторов: если указатель Child* неявно преобразуется в Parent*, то итераторы дают ошибку.
Пример:

#include <vector>

struct Base {};
struct Derived : Base {};

void derived_to_base_error()
{
    std::vector<Derived>::iterator i_d;
    std::vector<Base>::iterator i_b;
    i_b = i_d;
}

Помимо этого __normal_iterator ограничивает приведение между обычными и константными итераторами (только для чтения объекта).
Пример:

#include <vector>

struct Base {};

void const_contravariance()
{
    std::vector<Base>::iterator i_b; // Итератор
    std::vector<Base>::const_iterator *pi_b; // Указатель на константный итератор

    pi_b = &i_b; // Ошибка компиляции: cannot convert «std::vector<Base>::iterator*» to «std::vector<Base>::const_iterator*» in assignment
}

Подробнее про данную тему можно прочесть в статье What if vector<T>::iterator were just T*?

Типы итераторов

Существуют следующие типы итераторов:

  • iterator — обычный итератор для прямого обхода элементов контейнера с возможностью чтения/записи;
  • const_iterator — константный итератор для прямого обхода элементов контейнера только для чтения;
  • reverse_iterator — реверсивный итератор для обратного обхода элементов контейнера с возможностью чтения/записи;
  • const_reverse_iterator — константный реверсивный итератор для обратного обхода элементов контейнера только для чтения.

Для получения соответствующих итераторов контейнеры в C++ обладают следующими методами:

  • begin() — возвращает итератор, который указывает на первый элемент контейнера при наличии элементов и движется в прямом порядке, иначе его позиция совпадает с end();
  • end() — возвращает итератор, который указывает на следующую позицию за последним элементом;
  • rbegin() — возвращает итератор, который указывает на последний элемент контейнера при наличии элементов и движется в обратном порядке, иначе совпадает с rend();
  • rend() — возвращает итератор, который указывает на следующую позицию за первым элементом.

Примечание: существуют методы cbegin(), cend(), crbegin(), crend(), которые возвращают константные версии итераторов, которые обеспечивают доступ к элементам только в режиме чтения.

Примечание: если итераторы, возвращенные begin() и end(), не совпадают, то между ними есть как минимум один элемент.

Работа с итераторами

В реализации контейнеров присутствует определение соответствующего итератора через typedef. Пример объявления итератора std::vector для некого шаблонного типа T:

std::vector<T>::iterator it;

std::vector<T>::const_iterator c_it;
std::vector<T>::reverse_iterator r_it;
std::vector<T>::const_reverse_iterator cr_it;

Так же тип итератора можно получить через decltype — ключевое слово, которое возвращает тип выражения, не вычисляя его:

std::vector<T> vec;

decltype(vec.begin()) it;    // тип std::vector<T>::iterator
decltype(vec.cbegin()) c_it; // тип std::vector<T>::const_iterator

Начиная со стандарта C++11 можно использовать ключевое слово auto, которое указывает компилятору автоматически вывести тип переменной из её инициализатора:

std::vector<T> vec;

auto it = vec.begin();    // тип std::vector<T>::iterator
auto c_it = vec.cbegin(); // тип std::vector<T>::const_iterator

Пример работы с операторами для std::vector<Base>::iterator:

#include <vector>
#include <iostream>

struct Base
{
    int value;
};

int main()
{
    std::vector<Base> vec = { {1}, {2}, {3}, {4}, {5} };
    std::vector<Base>::iterator it = vec.begin();
    std::vector<Base>::iterator it2;

    // Присваивание
    it2 = it;

    // Разыменование
    std::cout << (*it).value << '\n'; // 1
    // Доступ через ->
    std::cout << it->value << '\n'; // 1

    // Инкремент
    std::cout << (++it)->value << '\n'; // 2
    std::cout << (it++)->value << '\n'; // 2, но итератор смещается на 3

    // Декремент
    std::cout << (it--)->value << '\n'; // 3, но итератор смещается на 2
    std::cout << (--it)->value << '\n'; // 1

    // Сравнение
    std::cout << "it в начале: " << (it == vec.begin()) << '\n'; // it в начале: 1
    std::cout << "it не в конце: " << (it != vec.end()) << '\n'; // it не в конце: 1
    std::cout << "it и i2 одинаковы: " << (it == it2) << '\n'; // it и i2 одинаковы: 1

    // Сдвиг
    it += 2;
    std::cout << it->value << '\n'; // 3
    it -= 1;
    std::cout << it->value << '\n'; // 2
    std::cout << (it - 1)->value << ' ' << (it + 1)->value << '\n'; // 1 3

    // Индексация
    std::cout << it2[2].value << '\n'; // 3

    // Вычисление расстояния
    std::ptrdiff_t dist = it2 - it;
    std::cout << "Расстояние между it2 и it: " << dist << '\n'; // Расстояние между it2 и it: -1
    std::cout << "Расстояние между it и it2: " << it - it2 << '\n'; // Расстояние между it и it2: 1

    // Сравнение порядка
    std::cout << "it < it2: "  << (it < it2)  << '\n'; // it < it2: 0
    std::cout << "it > it2: "  << (it > it2)  << '\n'; // it > it2: 1
    std::cout << "it <= it2: " << (it <= it2) << '\n'; // it <= it2: 0
    std::cout << "it >= it2: " << (it >= it2) << '\n'; // it >= it2: 1

    return 0;
}

Важное замечание: оператор доступа к элементу (operator->) имеет больший приоритет по отношению к инкрементам/декрементам, как следствие необходимо не забыть использовать круглые скобки для изменения приоритета вычислений.

Использование итераторов в цикле:

std::vector<int> vec = {1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); ++it)
    std::cout << *it << ' ';
std::cout << '\n';

Важное замечание: при работе с итераторами важно использовать проверку на неравенство (operator!=) с методом .end(), так как при использовании контейнеров с непоследовательным размещением элементов (например std::list) использование operator< может давать неверные результаты — текущий итератор может иметь больший адрес в памяти чем возвращаемый методом .end().

Начиная с C++11, для работы с контейнерами в цикле можно использовать range-based for, который является «синтаксическим сахаром» над итераторами:

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

for (int& ref : vec) // ref - ссылка на элемент
    ref++; // Изменяет элемент в контейнере

for (int copy : vec) // copy - копия элемента
    copy++; // Изменяет копию, элемент в контейнере остается прежним

for (auto& ref : vec) // auto& - ссылка, тип выводится автоматически
    ref++;

for (auto copy : vec) // auto - копия элемента, тип выводится автоматически
    copy++;

Важное замечание: использование значений (T, auto) создает копию элемента — изменение копии не влияет на содержимое контейнера, но если контейнер хранит тяжелые объекты, то копирование в цикле может быть дорогим.

Примечание: использование квалификатора const в цикле по ссылкам на объекты является полезным, так как обеспечивает доступ к объекту только в режиме чтения.

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

Реализация собственных итераторов

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

  • iterator_category — категория итератора, определяющая функциональность:
    • std::input_iterator_tag — минимальная категория для чтения из контейнера,
    • std::output_iterator_tag — минимальная категория для записи в контейнер,
    • std::forward_iterator_tag — несколько проходов в одну сторону,
    • std::bidirectional_iterator_tag — несколько проходов в обе стороны
    • std::random_iterator_tag — доступ к элементам по индексу, поддержка арифметики,
    • std::contiguous_iterator_tag — элементы расположены непрерывно;
  • value_type — тип элементов;
  • difference_type — тип данных для расстояния между двумя итераторами;
  • pointer — тип указателя на данные;
  • reference — тип ссылки на данные.

Пример заполнения параметров для шаблонного итератора используя using:

template <typename T>
class MyIterator
{
public:
    // Параметры итератора
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using pointer           = T*;
    using reference         = T&;
// ...
};

Пример заполнения параметров для шаблонного итератора используя typedef:

template <typename T>
class MyIterator
{
public:
    // Параметры итератора
    typedef std::random_access_iterator_tag iterator_category;
    typedef T                               value_type;
    typedef std::ptrdiff_t                  difference_type;
    typedef const T*                        pointer;
    typedef const T&                        reference;
// ...
};

Примечание: в компиляторе GCC используется именно typedef.

Для упрощения определения итератора и сокращения количества строк кода можно наследоваться от класса шаблонного итератора std::iterator, но данный способ помечен как deprecated для стандарта C++17, так как такой подход ограничивает область видимости типов, определяемых родительским классом.

template <typename T>
class MyIterator : std::iterator<std::random_access_iterator_tag, T>
{
public:
// В данном случае не требуется явно указывать параметры
     value_type data; // Даст ошибку компиляции: «value_type» не является именем типа
     typename std::iterator<std::random_access_iterator_tag, T>::value_type data; // Допустимо к использованию, но слишком громоздко.
// ...
};

Следующим этапом необходимо определить конструктор и операторы доступа к данным. В качестве примера будем хранить указатель 

template <typename T>
class MyIterator
{
public:
//...
    // Конструктор
    MyIterator(T* p = nullptr) : ptr(p) {} 
    // Операторы доступа к данным
    T& operator*() const { return *ptr; }
    T* operator->() const { return ptr; }
//...
private:
    pointer ptr; // pointer определен в параметрах итератора, описанных ранее
};

А так же оставшиеся методы для взаимодействия с итератором:

template <typename T>
class MyIterator
{
public:
//...
    // Операторы сдвига
    MyIterator& operator++() { ++ptr; return *this; }
    MyIterator operator++(int) { MyIterator tmp = *this; ++(*this); return tmp; }
    MyIterator& operator--() { --ptr; return *this; }
    MyIterator operator--(int) { MyIterator tmp = *this; --(*this); return tmp; }
    MyIterator operator+(difference_type n) const { return iterator(ptr + n); }
    MyIterator operator-(difference_type n) const { return iterator(ptr - n); }
    difference_type operator-(const MyIterator& other) const { return ptr - other.ptr; }
    T& operator[](difference_type n) { return ptr[n]; }

    // Операторы сравнения
    bool operator==(const MyIterator& other) const { return ptr == other.ptr; }
    bool operator!=(const MyIterator& other) const { return ptr != other.ptr; }
    bool operator<(const MyIterator& other) const { return ptr < other.ptr; }
    bool operator<=(const MyIterator& other) const { return ptr <= other.ptr; }
    bool operator>(const MyIterator& other) const { return ptr > other.ptr; }
    bool operator>=(const MyIterator& other) const { return ptr >= other.ptr; }
//...
};

Итоговая реализация имеет вид:

template <typename T>
class MyIterator
{
public:
    // Параметры итератора
    typedef std::random_access_iterator_tag iterator_category;
    typedef T                               value_type;
    typedef std::ptrdiff_t                  difference_type;
    typedef const T*                        pointer;
    typedef const T&                        reference;

    // Конструктор
    MyIterator(T* p = nullptr) : ptr(p) {}
    // Операторы доступа к данным
    T& operator*() const { return *ptr; }
    T* operator->() const { return ptr; }

    // Операторы сдвига
    MyIterator& operator++() { ++ptr; return *this; }
    MyIterator operator++(int) { MyIterator tmp = *this; ++(*this); return tmp; }
    MyIterator& operator--() { --ptr; return *this; }
    MyIterator operator--(int) { MyIterator tmp = *this; --(*this); return tmp; }
    MyIterator operator+(difference_type n) const { return iterator(ptr + n); }
    MyIterator operator-(difference_type n) const { return iterator(ptr - n); }
    difference_type operator-(const MyIterator& other) const { return ptr - other.ptr; }
    T& operator[](difference_type n) { return ptr[n]; }

    // Операторы сравнения
    bool operator==(const MyIterator& other) const { return ptr == other.ptr; }
    bool operator!=(const MyIterator& other) const { return ptr != other.ptr; }
    bool operator<(const MyIterator& other) const { return ptr < other.ptr; }
    bool operator<=(const MyIterator& other) const { return ptr <= other.ptr; }
    bool operator>(const MyIterator& other) const { return ptr > other.ptr; }
    bool operator>=(const MyIterator& other) const { return ptr >= other.ptr; }
private:
    pointer ptr;
};

Для работы с данным итератором необходим контейнер с методами: begin/end, cbegin/cend, rbegin/rend, crbegin/crend.

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

  • пользовательский контейнер должен работать с алгоритмами STL (std::sort, std::for_each, std::copy, …) или использоваться в range-based for;
  • пользовательские правила обхода (обход только четных элементов, пропуск неинициализированных элементов, обход с нестандартным шагом и т.д.);
  • создание генераторов — данные не хранятся, а создаются в процессе работы программы.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Управление cookie