NSU Programming Программирование на C++ и Python

Итераторы

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

Определение и классификация итераторов

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

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

  • Input Iterator
    • Forward Iterator
      • Bidirectional Iterator
        • Random access Iterator
  • Output Iterator

Output итераторы можно разыменовывать в левой части выражений:

*a = t;

Input итераторы можно сравнивать с помощью операторов == и !=. Каждый следующий подкласс Input итератора расширяет функционал:

  • Forward Iterator могут выполнять роль Output итератора. Итераторы этого типа используются для перебора элементов с помощью оператора инкремента.
  • Bidirectional Iterator позволяет дополнительно к функциональности Forward Iterator использовать оператор декремента -- и перебирать последовательность в обратном направлении. Итератор двусвязного списка из стандартной библиотеки list::iterator является Bidirectional Iterator.
  • Random access Iterator позволяет получить доступ к произвольному элементы диапазона по индексу, поддерживают операторы сравнения <, <=, >, >= и арифметические операторы + и -. Итератор vector::iterator является Random access Iterator.

Если открыть документацию алгоритмов, которые мы рассматривали раньше, то можно уточнить наше понимание работы алгоритмов с итераторами: каждый алгоритм предъявляет требования к итератору, с которым его можно использовать. Например, один из вариантов алгоритма find определен так:

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

т.е. для работы с этим алгоритмом итератор должен всего лишь обладать возможностями Input Iterator. А вот как выглядит один из вариантов алгоритма sort:

template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );

Сортировка за “линеарифмическое” время требует доступа к элементам диапазона по индексу, поэтому алгоритм sort требует Random access Iterator.

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

Итераторы и цикл for

Перебрать в цикле все элементы контейнера set, как мы знаем, можно с помощью range-based цикла:

set<int> s{/* elements */};

for (int item : s) {
    /* Some logic */
}

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

set<int> s1{/* elements */};
set<string> s2{/* elements */};

auto it1 = s1.begin();
auto it2 = s2.begin();

for (; it1 != s1.end() && it2 != s2.end(); ++it1; ++it2) {
    /* Some logic */
}

Стандартные контейнеры предоставляют обратные итераторы reverse_iterator, которые позволяют перебрать элементы диапазона в обратном порядке, например:

list<double> l {/* items */};
for (auto it = l.rbegin(); it != rend(); ++it) { /* */ }

Наконец, если мы работаем с константным объектом, либо если мы хотим избежать случайной модификации элементом диапазона, то следует использовать константный итератор const_iterator и методы cbegin() и cend():

const vector<int> v {/* */};
for (auto it = v.cbegin(); it != v.cend(); ++it) { /* */ }

Конструирование контейнеров с помощью итераторов

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

vector<int> v{6,2,8,3,2,6,1,2,4};
set<int> s(v.begin(), v.end());  // {1,2,3,4,6,8}

Еще один пример, который выглядит несколько непривычно, позволяет с помощью итератора istream_iterator прочитать все объекты из стандартного потока ввода в vector, а затем с помощью итератора ostream_iterator и алгоритма copy передать все элементы вектора в стандартный поток вывода:

#include <vector>
#include <iostream>
#include <iterator>  // istream_iterator, ostream_iterator
using namespace std;

int main() {
    vector<int> v {istream_iterator<int>(cin), istream_iterator<int>()};
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, ", "));

    return 0;
}

Отметим, что istream_iterator<int>(), как и нулевой указатель для списков, является универсальной меткой конца всех потоков данного типа.

Вставка объектов с помощью back_inserter

Последний пример, который мы рассмотрим, использует итератор back_insert_iterator, который позволяет добавлять элементы в конец контейнера:

#include <vector>
#include <iterator>  // back_inserter
using namespace std;

int main() {
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {4, 5, 6};
  
    copy(v1.begin(), v1.end(), back_inserter(v2));  // v2 = [4,5,6,1,2,3]
}

Функция back_inserter создает для нас нужный итератор. Без этой функции нам пришлось бы написать back_insert_iterator<std::vector<int>>(v).

Резюме

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

Документация