В процессе разработки мини-библиотеки файлового ввода я изучал код реализации функций/методов работы с файлами в стандартных библиотеках различных языков программирования, в том числе и Rust.
Глаз зацепился за реализацию итератора чтения файла по строкам. Для реализации итератора в Rust достаточно определения всего одной функции
next()
!Это маленькое открытие сподвигло меня к изучению того, как реализованы итераторы в других языках программирования.
В данной статье я поделюсь результатами этого небольшого исследования, а также представлю новую модель итераторов, которую я планирую сделать основной для языка 11l, и которую можно уже сейчас использовать в C++ проектах посредством простого адаптера (вот пример использования).
Но сначала хотелось бы устранить путаницу в терминологии, которую внёс C++. То, что в C++ принято называть итератором, в других языках называют чаще курсором. А итератор лишь обеспечивает возможность обхода итерируемого объекта. Его можно получить напрямую у контейнера [или любого другого итерируемого объекта] методом
iter()
в Rust, __iter__()
в Python, iterator()
в Java, GetEnumerator()
в C# или аналогичным (в этом случае будет производиться обход по всем элементам этого контейнера). Его [итератор] возвращают методы наподобие reversed()
/rev()
[позволяет обойти все элементы контейнера в обратном порядке], filter()
[обходит только элементы, удовлетворяющие определённому условию/предикату] и т.п.Мне было интересно, есть ли похожая на C++ модель итераторов в родственных языках, например в D, и поиском ‘d lang end iterator’ я вышел на тему форума языка D под названием ‘Iterators and Ranges: Comparing C++ to D to Rust’. Тема посвящена одноимённому докладу, наиболее интересную часть которого можно выразить в табличке на одном из слайдов.
![](https://habrastorage.org/webt/pk/bs/8g/pkbs8gwwydlw0qcbfb2c4_ng9zi.png)
Автор доклада выделяет 3 базовые операции, которые должны быть реализованы в итераторе:
- read — получение текущего элемента итерируемого объекта;
- advance — переход к следующему элементу итерируемого объекта;
- done? — проверка, остались ли ещё элементы в итерируемом объекте или нет.
В таблице на примере реализации этих трёх операций представлено сравнение моделей итераторов в языках программирования C++, D, C#, Rust, Python и Java.
Как можно заметить, C++ выделяется из всех остальных представленных в таблице языков необходимостью в дополнительной сущности last [точнее after_last, он же
end()
], т.к. в C++ под "итератором" понимается навороченный указатель.Данная табличка, хоть и красивая, но, к сожалению, не достаточно исчерпывающая. К примеру, новая модель итераторов в 11l в логике данной таблицы совпадает с моделью C#. Однако, фактически эти модели итераторов отличаются. Поэтому для более наглядного сравнения моделей итераторов я приведу псевдокод их обхода во всех языках программирования, представленных в этой таблице:
C++:
for (auto it = collection.begin(); it != collection.end(); ++it) {
...*it...
}
D:
for (auto r = collection.range(); !r.empty(); r.popFront()) {
...r.front()...
}
Python:
var it = collection.__iter__();
while (true) {
try {
let current = it.__next__();
...current...
}
catch (StopIteration) {
break;
}
}
Rust:
auto it = collection.iter();
while (auto current = it.next()) {
...*current...
}
Java:
Iterator it = collection.iterator();
while (it.hasNext()) {
var current = it.next();
...current...
}
C#:
var it = collection.GetEnumerator();
while (it.MoveNext()) {
...it.Current...
}
11l:
if (auto it = collection.iter()) do {
...it->current()...
} while (it->advance());
Для сравнения удобства различных моделей итераторов на практике я реализовал итераторы для нескольких типовых задач и результаты этого сравнения свёл в следующую таблицу.
(«+» означает «удобно», «−» — неудобно и «0» — не очень удобно.)
Языки программирования | Массив/Диапазон | Связный список | Чтение файла по строкам | Обход директории на диске |
---|---|---|---|---|
C++ | + | 0 [1] | 0 [4] | − |
D | + | + | 0 [4] | 0 |
Python/Rust | + | 0 [2] | + | − |
Java | + | 0 [2] | − [4][5] | − |
C# | 0 [3] | − [3] | + | − [3] |
11l | + | + | 0 [6] | 0 |
yield в Nim, Python и др. языках | + | + | + | + |
- В последнем узле связного списка в поле
next_node
удобно хранить просто нулевой указатель, который и является признаком окончания списка. Но если методend()
будет возвращать нулевой итератор, то для сравнения он сгодится, но такой итератор нельзя назвать полноценным C++-итератором, т.к. операцию--
к нему применить так просто не получится. Впрочем, для односвязного списка это не актуально, т.к. итератор односвязного списка в любом случае не поддерживает операцию--
. - Из-за того, что метод
next()
возвращает текущий элемент после того, как переходит к следующему, текущий элемент приходится предварительно запоминать/сохранять во временной вспомогательной переменнойresult
. - Неудобство в том, что
MoveNext()
не только выполняет проверку существования следующего элемента итерируемого объекта, но и переходит к следующему элементу, поэтому итератор изначально должен указывать на «минус первый» элемент, либо в итератор необходимо добавить специальный флаг, чтобы при первом вызовеMoveNext()
перехода к следующему элементу не происходило. - Приходится хранить в итераторе дополнительный флаг
has_next
и при конструировании итератора осуществлять чтение строки с инициализацией этого флага. - Необходимость реализации метода
hasNext()
значительно усложняет [по сравнению с Python и Rust] код итератора, т.к. приходится хранить следующую строку, которую необходимо запоминать/сохранять во временной вспомогательной переменной для возврата методомnext()
. - Требуется дополнительная логика [не сложная, но и не тривиальная] в методе получения итератора.
Новая модель итераторов
Как видно из вышеприведённой таблицы, новая модель итераторов [используемая в 11l] показывает себя в целом немного лучше моделей других языков, находясь примерно на одном уровне по удобству с моделью итераторов языка D (которые называют диапазонами). И хотя диапазоны в D требуют реализации трёх методов (empty, front, popFront), а итераторы 11l — всего двух (current и advance), это различие нивелируется тем, что логика метода empty() переходит в метод получения итератора, который, в отличие от D и всех остальных языков, возвращает не
Iterator
, a Iterator?
(Nullable[Iterator]
или std::optional<Iterator>
в C++).Расскажу вкратце, как я пришёл к новой модели итераторов. Большей частью, это было интуитивное решение, которое родилось в процессе реализации наиболее сложного типа итераторов из представленных — итератора по директории с фильтром для различных операционных систем. Мне нравилась модель Rust, и для простых случаев она работает хорошо, но реализовать итератор обхода директории в этой модели оказалось очень не удобно (можете сами посмотреть на код реализации метода next). Модель D более практична и достаточно удобна во всех случаях, но показалась мне избыточной — метод empty() в итераторе смотрится неуместно.
В попытке «избавиться от него» мне сначала пришла такая безумная идея — чтобы при попытке итерирования контейнера сначала вызывался метод
empty()
(не у итератора/диапазона, а у самого контейнера!) и итерация начиналась только в случае, когда он вернул false
.if (!collection.empty()) {
auto it = collection.iter();
do {
...it.current()...
} while (it.advance());
}
Но в таком случае возникает проблема с итерируемыми объектами, у которых нет метода empty(). Например, с тем же итератором обхода директории или с итератором чтения файла по строкам. В итоге, я не придумал ничего лучше, чем вынести логику метода empty() в метод получения итератора [iter()]. Считаю, это более правильно, чем в диапазонах D, т.к. метод empty() должен вызываться всего один раз перед началом итерирования и в итераторе ему делать нечего.В качестве названия метода для получения текущего элемента итерируемого объекта я рассматривал варианты
item()
и current_element()
, но остановился на current()
, т.к. именно такое имя используется в языках C# [только с большой буквы — Current
] и PHP. Для перехода к следующему элементу можно было бы использовать имя из C# — moveNext()
, но это какое-то странное редкое словосочетание и работает MoveNext()
из C# немного не так, как аналогичный метод в новой модели. Поэтому я решил взять название из доклада ‘Iterators and Ranges: Comparing C++ to D to Rust’ для операции, соответствующей этому методу — “advance”. Хотя метод advance()
в новой модели выполняет также и операцию “done?”, я решил не отражать это в его названии.yield
Но безусловным лидером по удобству несомненно является
yield
. Просто посмотрите на код функции iterate()
для любого итератора из моей реализации. Обход директории реализуется всего 8-ю строками понятного и легко читаемого кода, в то время как большинство реализаций итераторов требуют более 40-ка строк кода, и все эти реализации достаточно трудны для понимания.Почему тогда я не стал поступать так же, как автор языка Nim, в котором никаких моделей итераторов нет, а есть только yield?
Потому, что эффективно реализовать yield в компилируемом языке программирования не так просто. Иначе бы yield давно уже был в C++. Особенно непросто учесть случаи вызова yield в рекурсивных функциях (а это может использоваться например при рекурсивном обходе директорий). В том же Nim пришлось разделять
Размышления на тему [не]оптимальности модели итераторов в Python
Почему в Python не сделано как в Rust? Т.е. почему бы вместо порождения исключения
StopIteration
не возвращать None
?Потому, что в контейнере вполне может оказаться элемент со значением
None
.И дело в том, что [хорошо это или плохо, но] в Python нет такой вещи как
Some(None)
, а есть только просто None
. Т.е. если в Rust функция next()
может вернуть None
(что будет означать окончание итерирования), а может вернуть Some(None)
(что будет означать следующий элемент, имеющий значение None
), то в Python так сделать не получится (но и следующий элемент в Python можно возвращать просто как el
, а не Some(Some(el))
как приходится делать в Rust [для контейнеров, элементы в которых имеют тип Option
, т.е. могут быть None
]).На первый взгляд решение Python кажется неудачным: возбуждать исключение — ведь это очень дорого, и это приходится делать в каждом цикле в программе [кроме тех, где срабатывает ранний выход из цикла по
break
/return
].Но, во-первых, конкретно в Python это не очень дорого. И, во-вторых, это всего лишь стереотип [то, что возбуждение исключения — это всегда очень дорого], который 11l пытается разрушить посредством разделения исключений на два рода (подробнее про два рода исключений можно почитать в документации к 11l). При этом
StopIteration
разумно сделать исключением первого рода. В этом случае «порождение» этого исключения будет фактически означать возврат функцией next()
специального значения, являющегося признаком окончания итерации. Производительность при этом будет на уровне функции next()
в языке Rust, возвращающей Option
.P.S. Недавно я опубликовал итоги голосования/опроса [про получение системного времени с помощью std::chrono] в комментарии к моей предыдущей статье.
Комментарии (6)
mentin
31.08.2024 22:03+1Хорошая классификация итераторов, спасибо.
Наверное после разбора разных схем и отличий вашей схемы от с# и D можно расширить табличку из слайда ещё одной колонкой, start. Start у всех будет совпадать с done? кроме 11l. Концептуально табличка хороша.
tzlom
31.08.2024 22:03+2С++ итераторы у вас реализованы некорректно- begin() и end() должны возвращать одинаковый тип, ни один стандартный алгоритм из <algorithm> не будет работать с вашими итераторами.
И это кстати общий случай который 11l ломает- для итераторов в таком стиле каждый алгоритм требует быть определённым для пустого begin() - не удобно, раздуваем итератор (т.к optional теперь деталь реализации итератора)
Касательно реализации итератора по строкам - во первых странно строить новые типы итераторов на базе iostream который сам итератор и понятно что получается сложно местами. has_next можно убрать если проверять поток на окончание.
Из C# итератора вы выкинули главное его свойство - ленивость(создание итератора не запускает чтение данных)
С итерацией по директориям вы тоже перемудрили.
Ну и итераторы это то где как раз уместно оптимизировать производительность вплоть до инструкций.
В общем тема интересная, но над содержанием и выводами надо критически поработать.
KanuTaH
Ну так-то
co_yield
уже года 4 есть в C++, а в C++23 добавили к нему некоторую библиотечную обвязку, например,std::generator
, который превращает корутину с этимco_yield
в нечто итерируемое. Правда, @Kelbon скажет (и покажет), что генератор можно было бы сделать и получше, но это детали. Если не нравится стандартный генератор, то можно написать свой, для этого в языке все есть.Kelbon
в дереве где всего одно значение это не так впечатляюще выглядит, но с директориями это классический сценарий для рекурсивного генератора