В процессе разработки мини-библиотеки файлового ввода я изучал код реализации функций/методов работы с файлами в стандартных библиотеках различных языков программирования, в том числе и 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’. Тема посвящена одноимённому докладу, наиболее интересную часть которого можно выразить в табличке на одном из слайдов.
Вот в этой.
Автор доклада выделяет 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());
Если интересно, то вот код обхода итератора на том языке программирования, к которому он относится
C++:
D:
Python:
Rust:
Java:
C#:
11l:
for (auto it = collection.begin(); it != collection.end(); ++it) {
...*it...
}
D:
for (auto r = collection[]; !r.empty; r.popFront()) {
...r.front...
}
Python:
it = collection.__iter__()
while True:
try:
current = it.__next__()
except StopIteration:
break
...current...
Rust:
let mut it = collection.iter();
while let Some(current) = it.next() {
...current...
}
Java:
var it = collection.iterator();
while (it.hasNext()) {
var current = it.next();
...current...
}
C#:
var it = collection.GetEnumerator();
while (it.MoveNext()) {
...it.Current...
}
11l:
if var it = collection.iter()
loop
...it.current...
if !it.advance()
loop.break
Для сравнения удобства различных моделей итераторов на практике я реализовал итераторы для нескольких типовых задач и результаты этого сравнения свёл в следующую таблицу.
(«+» означает «удобно», «−» — неудобно и «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());
}
В качестве названия метода для получения текущего элемента итерируемого объекта я рассматривал варианты
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] в комментарии к моей предыдущей статье.
