зачем нужны итераторы c
Ленивые итераторы и диапазоны в C++
Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++.
Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку.
Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator ).
Данная публикация — это краткий ликбез о том, что такое ленивые итераторы и диапазоны, зачем они нужны и как ими пользоваться.
Содержание
Итератор
Начнём с простого. Что вообще такое итератор?
Понять суть концепции довольно легко. Сам по себе итератор — это обобщение указателя. При этом главное, что нужно знать — это два способа взаимодействия с итератором:
И в эти взаимодействия мы можем внедряться и переопределять их так, как нам нужно.
Ленивость
Внедрение в операции над диапазонами может быть сколь угодно хитрым и сложным (простые примеры я привёл ниже). Ленивость же состоит в том, что нет никаких промежуточных результатов. Все вычисления происходят только тогда, когда вызываются операции разыменования или продвижения.
Допустим, у нас есть некая последовательность элементов, заданная двумя итераторами: на начало и конец этой последовательности (при этом конец достижим из начала). Теперь мы преобразуем оба этих итератора каким-то способом и получаем два новых итератора. Если преобразование итераторов корректно, т.е. образ конца первой последовательности достижим из образа начала первой последовательности, то мы получили новую последовательность. При этом длина и элементы новой последовательности могут отличаться от длины и элементов исходной.
В этом и состоит ленивость — мы получили новую последовательность без изменений в старой. Мы не трогали хранимые объекты, а только переопределили способ их отображения и обхода по ним.
Transform Iterator
Он оборачивает некий исходный итератор и при разыменовании возвращает результат преобразования над разыменованным значением исходного итератора.
Filter Iterator
Он оборачивает продвижение, причём относительно «хитрым» образом. Он выбрасывает из рассмотрения все элементы исходной последовательности, которые не удовлетворяют заданному предикату. Единственное отличие — обёрнутый итератор сразу же позиционируется на нужном элементе, если у исходной последовательности есть префикс, все элементы которого не удовлетворяют предикату.
Ленивые диапазоны
Итератор — это обобщение указателя. Поэтому итератор, как и указатель, сам по себе не знает, когда нужно остановиться. Имея только итератор на начало последовательности, нельзя сказать, где конец этой последовательности. Поэтому мы объединяем пару итераторов — начало и конец — в диапазон.
При этом диапазон — это уже более сложная конструкция, и у него другой интерфейс, похожий на интерфейс контейнеров:
Разница только в том, что диапазон не владеет элементами, которые он задаёт. Хотя бы потому что канонический диапазон — это просто пара итераторов (к примеру, std::equal_range ).
Transform Range
На основе преобразующих итераторов можно собрать диапазон (см. boost::iterator_range ).
Stride
Он оборачивает исходный диапазон так, что в новом диапазоне остаются только кратные позиции исходного диапазона.
Компоновка
После того, как мы научились создавать диапазоны, нам не составит никакой сложности скомбинировать их в цепочку.
Например, если мы хотим для некоей последовательности чисел:
то можно это сделать так:
Ещё раз хочу подчеркнуть, что этот код не производит никаких вычислений. Он только сохраняет «схемы» работы с диапазоном, а настоящие вычисления будут происходить только во время продвижения или разыменования обёрнутого итератора.
Суть итераторов и диапазонов
Помимо C++, в некоторых языках программировани также существует концепция под названием «итератор», но эта концепция зачастую имеет какой-то свой, альтернативный смысл.
К примеру, «итераторы» в языках Java и C# знают свой предел. С точки зрения языка C++ это, скорее, диапазоны.
В C++ итератор — это именно обобщение указателя. По сути указатель — это самый сильный (или наиболее конкретный) итератор, причём иерархия следующая:
Диапазон же можно рассматривать именно как пару итераторов (даже если это на самом деле не так). Диапазон уже знает, где у него конец, может накладывать дополнительную логику на операции с итераторами и т.д. Также диапазон может быть сконвертирован обратно в итераторы (потому что диапазон — это пара итераторов, как уже было сказано выше).
Такое разделение на итераторы и диапазоны помогает создавать универсальные, гибкие и эффективные интерфейсы для операций над последовательностями.
Один из примеров создания сложной операции над диапазонами я привёл в статье Ленивые операции над множествами в C++.
Урок №198. Итераторы STL
Обновл. 15 Сен 2021 |
Итератор — это объект, который способен перебирать элементы контейнерного класса без необходимости пользователю знать реализацию определенного контейнерного класса. Во многих контейнерах (особенно в списке и в ассоциативных контейнерах) итераторы являются основным способом доступа к элементам этих контейнеров.
Функционал итераторов
Об итераторе можно думать, как об указателе на определенный элемент контейнерного класса с дополнительным набором перегруженных операторов для выполнения четко определенных функций:
Оператор * возвращает элемент, на который в данный момент указывает итератор.
Оператор ++ перемещает итератор к следующему элементу контейнера. Большинство итераторов также предоставляют оператор −− для перехода к предыдущему элементу.
Каждый контейнерный класс имеет 4 основных метода для работы с оператором = :
метод begin() возвращает итератор, представляющий начальный элемент контейнера;
метод end() возвращает итератор, представляющий элемент, который находится после последнего элемента в контейнере;
метод cbegin() возвращает константный (только для чтения) итератор, представляющий начальный элемент контейнера;
метод cend() возвращает константный (только для чтения) итератор, представляющий элемент, который находится после последнего элемента в контейнере.
Может показаться странным, что метод end() не указывает на последний элемент контейнера, но это сделано в целях упрощения использования циклов: цикл перебирает элементы до тех пор, пока итератор не достигнет метода end(), и тогда уже всё — «Баста!».
Наконец, все контейнеры предоставляют (как минимум) два типа итераторов:
container::iterator — итератор для чтения/записи;
container::const_iterator — итератор только для чтения.
Рассмотрим несколько примеров использования итераторов.
Итерация по вектору
Заполним вектор 5-ю числами и с помощью итераторов выведем значения вектора:
Итераторы (C#)
Итератор можно использовать для прохода по коллекции, такой как список или массив.
Метод итератора или метод доступа get выполняет настраиваемую итерацию по коллекции. Метод итератора использует оператор yield return для поочередного возврата каждого элемента. При достижении инструкции yield return текущее расположение в коде запоминается. При следующем вызове функции итератора выполнение возобновляется с этого места.
Итератор используется из клиентского кода с помощью оператора foreach или с помощью запроса LINQ.
Простой итератор
Создание класса коллекции
Использование итераторов с универсальным списком
Помимо универсального метода GetEnumerator должен быть реализован и неуниверсальный метод GetEnumerator. Это связано с тем, что IEnumerable наследуется от IEnumerable. Неуниверсальная реализация подчиняется универсальной реализации.
Сведения о синтаксисе
Техническая реализация
Чтобы просмотреть операции компилятора, воспользуйтесь средством Ildasm.exe, чтобы просмотреть код промежуточного языка Майкрософт, создаваемый для метода итератора.
Итераторы не поддерживают метод IEnumerator.Reset. Для повторной итерации сначала необходимо получить новый итератор. Вызов Reset в итераторе, который возвращается методом итератора, вызывает исключение NotSupportedException.
Дополнительные сведения см. в спецификации языка C#.
Использование итераторов
Инкапсулирование построения списка в итераторе. В методе итератора можно построить список, а затем выдавать каждый результат в цикле.
Недооценённые итераторы
Речь пойдет о стандартной библиотеке шаблонов STL. Будут рассмотрены существующие типы итераторов и их классификация, а также будут предложены несколько новых обёрток над итераторами. Которые позволят в некоторых случаях избежать лямбда-выражений, которых до С++11 как бы и нет.
Вступительное слово
Одной из основных парадигм данной библиотеки было разделение двух сущностей. Контейнеров и алгоритмов. Но для непосредственного воздействия алгоритмом на данные контейнера пришлось ввести промежуточную сущность — итератор.
Итераторы позволили алгоритмам получать доступ к данным, содержащимся в контейнере, независимо от типа контейнера. Но для этого в каждом контейнере потребовалось определить класс итератора. Таким образом алгоритмы воздействуют на данные через итераторы, которые знают о внутреннем представлении контейнера.
Типы итераторов в STL
Помимо итераторов, осуществляющих доступ к данным определённого контейнера в библиотеке STL имеются ещё несколько итераторов:
1. back_insert_iterator и front_insert_iterator
2. insert_iterator
3. istream_iterator и ostream_iterator
Итераторы типов back_insert_iterator и front_insert_iterator при модификации содержимого осуществляют вставку элемента методом push_back() или push_front(). Операции перемещения к предыдущему/следующему элементу контейнера эти итераторы попросту игнорируют.
Итератор insert_iterator при модификации осуществляет вставку данных. Ему в конструктор передаются контейнер и итератор на позицию, куда следует вставлять данные.
Итераторы istream_iterator и ostream_iterator осуществляют считывание данных из потока и запись данных в поток. В конструкторы этих итераторов необходимо передать входной или же выходной поток.
Классификация итераторов
Существующая классификация итераторов насчитывает 5 категорий итераторов:
1. Input iterator
2. Output iterator
3. Forward iterator
4. Bidirectional iterator
5. Random access iterator
Разработка декоратора итератора
Для реализации нескольких следующих идей необходимо было реализовать обертку или декоратор (wrapper). Декоратор итератора должен иметь ту же самую категорию, что и оборачиваемый итератор, а значит предоставлять тот же самый набор методов. В соответствии с приведённой таблицей категорий было разработано:
1. Пять классов-примесей (mixin), реализующих не пересекающиеся наборы методов.
2. Шаблонный класс декоратора, параметризуемый категорией итератора.
3. Пять специализаций шаблона, отличающиеся набором подмешиваемых примесей.
4. Фабрика для удобного (без явных шаблонных параметров) обёртывания итератора.
[На этот код можно взглянуть здесь, он почти работает]
После небольшого обсуждения получившейся структуры с одним хорошим человеком была выработана новая структура. Не такая насыщенная шаблонами и более лаконичная. Решено было реализовать все методы всех категорий итераторов в одном шаблонном классе, параметризуемом категорией итератора. Было использовано следующее свойство языка C++: компилируются только те методы шаблонного класса, вызов которых реально осуществляется.
Таким образом, если потребуется обернуть итератор категории Input будут скомпилированы только те методы которые, относятся к категории Input и вызываются. При попытке вызова метода не принадлежащего этой категории — возникнет ошибка компиляции. А это как раз то к чему мы стремились.
Битовый итератор
Битовый итератор позволяет обходить элементы контейнеров побитно. Итератор может использоваться как для считывания, так и для записи значений битов. У итератора имеются параметры:
1. В каком порядке обходить байты элементов контейнера
2. В каком порядке обходить биты в байтах
Полевой итератор
Полевой итератор представляет из себя итератор, который при разыменовывании возвращает значение одного из полей структуры. Может оказаться весьма полезен для поиска объекта по значению одного из полей. Пример использования:
Макрос fieldof(Class,Field) выглядит следующим образом:
UPD
Как заметил пользователь mayorovp, можно было обойтись указателем на поле класса:
Сортирующий итератор
Сортирующий итератор представляет из себя итератор, выполняющий обход элементов в порядке их сортировки. Элементы контейнера не модифицируются в процессе обхода итератором. Плюсом в данном случае является то, что время на сортировку не тратится (нет определённого участка времени отведённого под сортировку).
При перемещении итератора к следующему элементу осуществляется поиск наименьшего элемента среди оставшихся, которые больше-или-равны предыдущему. Таким образом сложность алгоритма получается O(N 2 ), но специального времени отведённого под сортировку нет. Сортировка осуществляется в процессе обращения к данным. Обращение через итераторы осуществляется пошаговое — сортировка тоже пошаговая.
Итератор параметризуется порядком сортировки. По-умолчанию: сортировка по возрастанию.
Лекция 10. Стандартная библиотека (продолжение)
1 Итераторы и алгоритмы
1.1 Итераторы
Итератор представляет некоторую позицию в контейнере.
Основные операторы, работу с которыми поддерживает итератор:
Методы begin и end
Все контейнеры поддерживаются базовые функции, применяемые для перебора элементов при помощи итераторов:
Функции begin() и end() определяют полуоткрытый интервал [b, e), который содержит первый элемент, но выходит за пределы последнего элемента.
Полуоткрытый интервал обладает двумя достоинствами:
Пример
Константный итератор
В каждом контейнере определены два типа итераторов:
Инкремент
Категории итераторов
Итераторы контейнерных классов list, set, multiset, map и multimap являются двунаправленными.
Итераторы контейнерных классов vector и deque, а также итераторы строк являются итераторами произвольного доступа.
1.2 Алгоритмы
Вместо того чтобы реализовывать каждый алгоритм для каждого типа контейнера, достаточно реализовать его один раз для обобщенного типа контейнера.
Такой подход сокращает объем программного кода, делая библиотеку более мощной и гибкой.