При обсуждении алгоритмов стандартной библиотеки C++ мы постоянно использовали итераторы. Из контекста мы поняли, что итераторы используются для указывания на элементы контейнеров. Пришло время сформировать более полное представление об этих объектах, узнать какие типы итераторов существуют, рассмотреть еще несколько ситуаций, в которых полезно использование итераторов.
Итератор — это объект, который указывает на элемент в диапазоне элементов (например, в массиве), с помощью итератора можно перебирать элементы диапазона, используя определенный набор операций. Для итератора определены по крайней мере операторы инкремента (++) и разыменовывания (*).
Существует пять типов итераторов, организованных следующим образом:
Output итераторы можно разыменовывать в левой части выражений:
*a = t;
Input итераторы можно сравнивать с помощью операторов == и !=. Каждый следующий подкласс Input итератора расширяет функционал:
-- и перебирать последовательность в обратном направлении. Итератор двусвязного списка из стандартной библиотеки list::iterator является Bidirectional 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.
Теперь, когда мы разобрались с основными понятиями, рассмотрим несколько ситуаций, в которых полезно использовать итераторы.
Перебрать в цикле все элементы контейнера 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_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. Знание различных итераторов и их возможностей позволяет использовать контейнеры и алгоритмы стандартной библиотеки наиболее полно.