Итераторы в C ++

Всем привет!

Эта статья представляет собой резюме моей презентации, объясняющей тему итератора на языке C ++, 18.07.2018 на Встрече по C ++ из Барселоны.

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

Итератор - что, зачем и основы

Как указывает Википедия, итератор - это объект, который позволяет программисту перемещаться по контейнеру, не зная, как этот контейнер реализован.

Причина того, что контейнеры и алгоритмы STL так хорошо работают вместе, заключается в том, что они ничего не знают друг о друге, - Алекс Степанов

Для этого каждый итератор должен знать как начать и как закончить маршрут, который они определены в контейнере.

В C ++ каждый итератор рассматривается как указатель , и обычно, контейнер определяет две функции, называемые begin () и end (), определяя начало и конец контейнера в виде полуоткрытого интервала [начало, конец)

Я просто говорю нормально, потому что, поскольку Ricard указывает на Meetup, имена begin () и end () не нужно определять begin и end для использования в качестве итератора. Это необходимо только в том случае, если мы хотим обойти его, используя диапазон цикла for, представленный в C ++ 11.

Что касается функции end (), вы можете определить дозорного, чтобы выбрать, когда контейнер может закончиться. Для кода, который размещен в финале этой статьи, я выбрал nullptr, чтобы знать, где завершился итератор.

Поскольку Mikel указывает на Meetup, рекомендуется, чтобы функция end () возвращала указатель на следующий элемент последнего контейнера.

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

В C ++ программист определяет различные типы итераторов в перегрузке новых арифметических / ссылочных / присваивающих операторов.

Обязательными операторами, которые необходимо определить в классе, чтобы называть его «итератором», являются следующие три:! = (для сравнения итератора с end (), зная, как остановить), ++ (чтобы указать на следующий элемент контейнера) и =.

В функции, операторы которой перегружены внутри итератора, STL определяет пять различных категорий итераторов.

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

Как мы знаем, существуют разные типы контейнеров (например, вектор, связанный список, двусвязный список, двоичное дерево поиска, граф…), и очевидно, что для их обхода необходимы различные методы. (что то же самое, что и существование разных типов итераторов, тоже очевидно).

Например, связанный список, как он определен, может двигаться только вперед, а двойной связанный список может двигаться вперед и назад.

Как мы видим в этом простом примере, итератор, определенный в двойном связанном списке, имеет метод обхода, который не определен в связанном списке, для определения каждого контейнера.

В языке C ++ стандарт определяет пять различных категорий: ввод, вывод, пересылка, двунаправленный и случайный. Мы можем рассматривать эти типы как набор и внутренние наборы операторов перегрузки:

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

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

Особенности итератора

STL использует итераторы для своих алгоритмов, чтобы избежать повторной реализации всех из них для каждого конкретного случая, когда ему нужно пройти через разные стили контейнеров. Из-за различных типов категорий итераторов C ++ определяет черты итератора, которые программист должен указать, если он / она хочет наилучшей оптимизации при использовании алгоритма STL.

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

Используя связанный список, сложность поиска элемента составляет O (N), потому что фактический узел дает нам только значение и следующий узел в качестве информации, тем временем, используя вектор, мы можем применить двоичный поиск и уменьшить сложность до O (log N), потому что, используя вектор, мы могли получить доступ к каждому узлу, только зная позицию индекса.

С итераторами происходит то же самое. Алгоритму лучше знать, что контейнер может быть перемещен с помощью оператора + = (произвольный доступ) или только оператора ++ (вперед), чтобы выбрать лучший выбор для уменьшения сложности вычисляемого алгоритма.

Характеристики итератора следующие:

тип различия: тип расстояния между узлом и следующим.
тип значения: тип значения, на которое указывает итератор.
указатель: значение указателя, на которое указывает итератор.
ссылка: ссылочное значение, на которое указывает итератор.
Категория итератора: одна из следующих: random_access_iterator_tag, bidirectional_iterator_tag, forward_iterator_tag, output_iterator_tag и input_iterator_tag.

Вы можете получить более подробную информацию об этих здесь.

Эволюция итератора в языке C ++

Итератор в C ++ не так сильно изменился между C ++ 98 и C ++ 11.

Единственное отличие, которое мы можем заметить, заключается в том, что в C ++ 98 черты итератора определены с помощью синтаксиса typedef typename, в то время как в C ++ 11 он использует using синтаксис.

Наиболее существенное различие - начиная с C ++ 17, в котором разрешено использовать только свойства итератора в качестве атрибутов типа. Способ определения себя путем наследования итератора базового класса становится устаревшим.

А другие языки?

Другие языки, такие как Python, C # или Lua, представляют новую концепцию, относящуюся к итераторам, которая сегодня доступна только как экспериментальная в C ++ 2a: generator и yield.

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

Давайте объясним это лучше на примере кода Python:

def codeGenerator():
    mylist = range(5)
    for i in mylist:
        yield i*i

Когда вызывается codeGenerator (), он возвращает генератор, который является итератором, который можно пройти только один раз.

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

C ++ 2a: Итератор и совместная процедура - друзья.

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

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

В C ++ 2a будет реализовано три новых ключевых слова: co_yield, co_return и co_await.

Более подробную информацию о совместной подпрограмме в C ++ вы можете получить здесь.

Создание настраиваемого класса с его настраиваемым итератором

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

Код показывает нам следующие классы:

Узел: содержит данные значения и указатели влево / вправо на его дочерние элементы.
BST: класс дерева двоичного поиска, реализует методы вставки и поиска в качестве определения этой структуры данных.
База итератора: содержит черты итератора и комментирует часть кода, объявленную в C ++ 17 устаревшей. Он перегружает операторы, общие с другими итераторами, например! = И =
Предварительный заказ итератора: оператор + перегружен для обхода контейнера в предварительном порядке.
Итератор postorder: оператор + перегружен для обхода контейнера в postorder.
Предварительный порядок итератора: оператор + перегружен для обхода контейнера в порядке.

Поскольку Ricard указывает на встречу, код теряет семантику в итераторе C ++, потому что оператор ++ для каждого шага не O (1).

Я исправлю это в ближайшее время и отредактирую эту публикацию ☺.

Итераторы в C ++ - Meetup Cpp