Что такое итераторы и зачем они нужны
Смотрите. Пускай у вас есть контейнер. Неважно какой: map , vector , set . Он содержит набор элементов. И вы хотите сослаться не на весь контейнер, а на какое-то место в этом наборе элементов. Так чтобы от этого места можно было перейти вперёд/назад, и что-то в этом месте сделать: изменить элемент, вставить элемент, удалить элемент.
Как это сделать? Для массива вы в таких случаях пользуетесь индексом. set внутри является красно-чёрным деревом, так что вам понадобится ссылка на узел этого дерева. unordered_map использует хэш-таблицу, так что вам нужна пара из хэш-индекса и указателя на элемент внутри bucket’а.
Чтобы не приходилось писать алгоритмы, специфические для каждого контейнера, и были придуманы итераторы.
Итератор — структура данных, которая «указывает» на некоторый элемент контейнера, и (для некоторых контейнеров) умеет переходить к предыдущему/следующему элементу.
Если вы хотите реализовать итератор, помните, что существуют разные типы итераторов, в зависимости от операций, которые они предоставляют. Вот список возможных типов.
Если вы, например, хотите реализовать RandomAccessIterator , вам придётся определить конструктор копирования, оператор присваивания, деструктор, операции == , != , * , -> , конструктор без аргументов, ++ , — , += , + (2 шт.), -= , — (2 шт.), < , >, = . (Другие типы итераторов попроще.)
Итераторы
Реализовать интерфейсы IEnumerator и IEnumerable нетрудно. Но еще проще воспользоваться итератором, который представляет собой метод, оператор или аксессор, возвращающий по очереди члены совокупности объектов от ее начала и до конца. Так, если некоторый массив состоит из пяти элементов, то итератор данного массива возвратит все эти элементы по очереди. Реализовав итератор, можно обращаться к объектам определяемого пользователем класса в цикле foreach.
Обозначение yield служит в языке C# в качестве контекстного ключевого слова. Это означает, что оно имеет специальное назначение только в блоке итератора. А вне этого блока оно может быть использовано аналогично любому другому идентификатору. Следует особо подчеркнуть, что итератор не обязательно должен опираться на массив или коллекцию другого типа. Он должен просто возвращать следующий элемент из совокупности элементов. Это означает, что элементы могут быть построены динамически с помощью соответствующего алгоритма.
Для преждевременного прерывания итератора служит следующая форма оператора yield:
yield break;
Когда этот оператор выполняется, итератор уведомляет о том, что достигнут конец коллекции. А это, по существу, останавливает сам итератор. В итераторе допускается применение нескольких операторов yield. Но каждый такой оператор должен возвращать следующий элемент в коллекции.
представляет собой метод, общая форма которого приведена ниже:
public IEnumerable имя_итератора(список_параметров) < // . yield return obj; >где имя_итератора обозначает конкретное имя метода; список_параметров — от нуля до нескольких параметров, передаваемых методу итератора; obj — следующий объект, возвращаемый итератором. Как только именованный итератор будет создан, его можно использовать везде, где он требуется, например для управления циклом foreach.
Именованные итераторы оказываются весьма полезными в некоторых ситуациях, поскольку они позволяют передавать аргументы итератору, управляющему процессом получения конкретных элементов из коллекции. Например, итератору можно передать начальный и конечный пределы совокупности элементов, возвращаемых из коллекции итератором. Эту форму итератора можно перегрузить, расширив ее функциональные возможности.
Давайте рассмотрим пример использования итераторов:
using System; using System.Collections; namespace ConsoleApplication1 < class Letter < char ch = 'А'; int end; public Letter(int end) < this.end = end; >// Итератор, возвращающий end-букв public IEnumerator GetEnumerator() < for (int i = 0; i < this.end; i++) < if (i == 33) yield break; // Выход из итератора, если закончится алфавит yield return (char)(ch + i); >> // Создание именованного итератора public IEnumerable MyItr(int begin, int end) < for (int i = begin; i > > class Program < static void Main() < Console.Write("Сколько букв вывести? "); int i = int.Parse(Console.ReadLine()); Letter lt = new Letter(i); Console.WriteLine("\nРезультат: \n"); foreach (char c in lt) Console.Write(c + " "); Console.Write("\nВведите пределы\n\nMin: "); int j = int.Parse(Console.ReadLine()); Console.Write("Max: "); int y = int.Parse(Console.ReadLine()); Console.WriteLine("\nРезультат: \n"); foreach (char c in lt.MyItr(j,y)) Console.Write(c + " "); Console.ReadLine(); >> > Итераторы
Итератор — это объект, указывающий на элемент какого-то контейнера.
Итератор является абстракцией над концепцией указателей. Если указатели работают только с последовательными данными (массивами), то итераторы работают с любыми контейнерами — например со связными списками или деревьями поиска — причём в единообразном синтаксисе, что сильно помогает разработчикам библиотек избегать дублирования кода.
#Синтаксис
Чтобы получить элемент, на который указывает итератор it , необходимо воспользоваться оператором разыменования: *it . Если нужно перейти к следующему элементу надо использовать инкремент: ++it (постфиксного инкремента у итераторов нет).
У всех контейнеров есть какой-то первый и последний элемент. Итератор на первый элемент можно получить через a.begin() , а через a.end() можно получить итератор на некий фиктивный элемент, следующий последним. Таким образом, если проходить от a.begin() до a.end() не включительно, ты мы пройдём по всем элементам контейнера.
::iterator»
#Категории итераторов
Итераторы — очень важная часть интерфейса контейнера. Итераторы можно передавать в различные алгоритмы стандартной библиотеки, которым не обязательно знать про внутреннее устройство контейнера, но нужно знать про то, какие паттерны доступа к данным возможны.
Поэтому в зависимости от внутренней структуры, итераторы контейнера могут отвечать к одному из нескольких абстрактных классов с разными уровнями гарантий:
- input_iterator , поддерживающий только операции разыменования и инкремента — причём даже без гарантии, что после того, как был произведён инкремент, его предыдущие значения остались валидными. Как можно догадаться из названия, используется для потокового ввода.
- forward_iterator , помимо предыдущего гарантирующий что итераторы на какой-то конкретный элемент можно инкрементировать сколько угодно раз не опасаясь, что они исчезнут (что позволяет их использовать в алгоритмах, проходящих по данным несколько раз).
- bidirectional_iterator , помимо предыдущего поддерживающий возможность декремента ( it— ) — то есть перехода к предыдущему элементу.
- random_access_iterator , помимо предыдущего поддерживающий возможность переходить к элементу, который находится на каком-то расстоянии $k$ — it + k , it — k , it += k , it -= k — и находить расстояние между позициями, на которые указывают два итератора: например, выражение a — b вернет целое число — расстояние между двумя элементами коллекции, соответствующим итераторам a и b .
#Алгоритмы из STL
Например, итераторы std::vector относятся к random_access_iterator , и если вызвать функцию lower_bound из стандартной библиотеки, то она произведет бинарный поиск по элементам (предполагая, что они отсортированы в порядке неубывания):
Функция lower_bound возвращает итератор на первый элемент, не меньший заданного. Также есть upper_bound , возвращающий первый элемент, строго больший (в случае с int это то же самое, что найти lower_bound от x + 1 ).
Зная, что итераторы вектора поддерживают произвольный доступ, бинарный поиск будет работать за $O(n \log n)$, но для других структур это, возможно, будет не так.
Также по этой причине часто имеет смысл вместо сишных массивов использовать std::array , который является точно таким же массивом фиксированной длины, но поддерживает итераторы и вместе с ними все алгоритмы STL:
Особенности языков программирования
В этой статье будет дан обзор библиотеки STL с самого начального уровня, и до продвинутой, весьма полезной в ряде задач, функциональности.
Проще всего начать знакомство с STL со стандартных типов для хранения данных — контейнеров. Каждый раз, когда в программе возникает необходимость оперировать множеством элементов, в дело вступают контейнеры. Контейнер — это практическая реализация функциональности некоторой структуры данных. В языке C (не в C++) существовал только один встроенный тип контейнера: массив. Сам по себе массив имеет ряд недостатков: к примеру, размер динамически выделенного массива невозможно определить на этапе выполнения. Однако основной причиной для более внимательного ознакомления с контейнерами STL является отнюдь не вышеперечисленные недостатки массива. Истинная причина кроется несколько глубже. Дело в том, что в реальном мире структура данных, информацию о которых необходимо хранить, далеко не всегда удачно представима в виде массива. В большинстве случаев требуется контейнер несколько иной функциональности. К примеру, нам может потребоваться структура данных «множество строк», поддерживающая следующие функции:
— добавить строку к множеству;
— удалить строку из множества;
— определить, присутствует ли в рассматриваемом множестве данная строка;
— узнать количество различных строк в рассматриваемом множестве;
— просмотреть всю структуру данных, «пробежав» все присутствующие строки. Конечно, легко запрограммировать тривиальную реализацию функциональность подобной структуры данных на базе обычного массива. Но такая реализация будет крайне неэффективной. Для достижения приемлемой производительности имеет смысл реализовать хэш-таблицу или сбалансированное дерево, но задумайтесь: разве реализация подобной структуры данных (хэш либо дерево) зависит от типа хранимых объектов? Если мы потом захотим использовать ту же структуру не для строк, а, скажем, для точек на плоскости — какую часть кода придётся переписывать заново? Реализация подобных структур данных на чистом C оставляла программисту два пути. 1) Жёсткое решение (Hard-Coded тип данных). При этом изменение типа данных приводило к необходимости внести большое число изменений в самых различных частях кода. 2) По возможности сделать обработчики структуры данных независимыми от используемого типа данных. Иными словами, использовать тип void* везде, где это возможно. По какому бы пути реализации структуры данных в виде контейнера вы не пошли, скорее всего, никто другой ваш код понять, и тем более модифицировать, будет не в состоянии. В лучшем случае другие люди смогут им просто пользоваться. Именно для таких ситуаций существуют стандарты — чтобы программисты могли говорить друг с другом на одном и том же формальном языке. Шаблоны (Templates) в C++ предоставляют замечательную возможность реализовать контейнер один раз, формализовать его внешние интерфейсы, дать асимптотические оценки времени выполнения каждой из операций, а после этого просто пользоваться подобным контейнером с любым типом данных. Можете быть уверены: разработчики стандарта C++ так и поступили. В первой части курса мы на практике познакомимся с основными концепциями, положенными в основу контейнеров C++.