В процессе разработки мини-библиотеки файлового ввода я изучал код реализации функций/методов работы с файлами в стандартных библиотеках различных языков программирования, в том числе и 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 базовые операции, которые должны быть реализованы в итераторе:
  1. read — получение текущего элемента итерируемого объекта;
  2. advance — переход к следующему элементу итерируемого объекта;
  3. 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 и др. языках + + + +
  1. В последнем узле связного списка в поле next_node удобно хранить просто нулевой указатель, который и является признаком окончания списка. Но если метод end() будет возвращать нулевой итератор, то для сравнения он сгодится, но такой итератор нельзя назвать полноценным C++-итератором, т.к. операцию -- к нему применить так просто не получится. Впрочем, для односвязного списка это не актуально, т.к. итератор односвязного списка в любом случае не поддерживает операцию --.
  2. Из-за того, что метод next() возвращает текущий элемент после того, как переходит к следующему, текущий элемент приходится предварительно запоминать/сохранять во временной вспомогательной переменной result.
  3. Неудобство в том, что MoveNext() не только выполняет проверку существования следующего элемента итерируемого объекта, но и переходит к следующему элементу, поэтому итератор изначально должен указывать на «минус первый» элемент, либо в итератор необходимо добавить специальный флаг, чтобы при первом вызове MoveNext() перехода к следующему элементу не происходило.
  4. Приходится хранить в итераторе дополнительный флаг has_next и при конструировании итератора осуществлять чтение строки с инициализацией этого флага.
  5. Необходимость реализации метода hasNext() значительно усложняет [по сравнению с Python и Rust] код итератора, т.к. приходится хранить следующую строку, которую необходимо запоминать/сохранять во временной вспомогательной переменной для возврата методом next().
  6. Требуется дополнительная логика [не сложная, но и не тривиальная] в методе получения итератора.

Новая модель итераторов


Как видно из вышеприведённой таблицы, новая модель итераторов [используемая в 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 пришлось разделять итераторы функции с yield на 2 вида: первый приводит к раздуванию кода и не поддерживает рекурсию, а второй — менее производителен.

Размышления на тему [не]оптимальности модели итераторов в 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] в комментарии к моей предыдущей статье.

Комментарии (9)


  1. KanuTaH
    31.08.2024 22:03
    +1

    Потому, что эффективно реализовать yield в компилируемом языке программирования не так просто. Иначе бы yield давно уже был в C++. Особенно непросто учесть случаи вызова yield в рекурсивных функциях (а это может использоваться например при рекурсивном обходе директорий).

    Ну так-то co_yield уже года 4 есть в C++, а в C++23 добавили к нему некоторую библиотечную обвязку, например, std::generator, который превращает корутину с этим co_yield в нечто итерируемое. Правда, @Kelbon скажет (и покажет), что генератор можно было бы сделать и получше, но это детали. Если не нравится стандартный генератор, то можно написать свой, для этого в языке все есть.


    1. Kelbon
      31.08.2024 22:03

      в дереве где всего одно значение это не так впечатляюще выглядит, но с директориями это классический сценарий для рекурсивного генератора

      // псевдокод не обрабатывающий много чего
      generator<file_entry> directory_recursive(filesystem::path p) {
        for (auto&& entry : entriees_of(p)) {
          if (entry.is_direectory())
            co_yield elements_of(directory_recursive(entry.path));
          else
            co_yild entry;
        }
      }


  1. mentin
    31.08.2024 22:03
    +1

    Хорошая классификация итераторов, спасибо.

    Наверное после разбора разных схем и отличий вашей схемы от с# и D можно расширить табличку из слайда ещё одной колонкой, start. Start у всех будет совпадать с done? кроме 11l. Концептуально табличка хороша.


  1. tzlom
    31.08.2024 22:03
    +3

    С++ итераторы у вас реализованы некорректно- begin() и end() должны возвращать одинаковый тип, ни один стандартный алгоритм из <algorithm> не будет работать с вашими итераторами.

    И это кстати общий случай который 11l ломает- для итераторов в таком стиле каждый алгоритм требует быть определённым для пустого begin() - не удобно, раздуваем итератор (т.к optional теперь деталь реализации итератора)

    Касательно реализации итератора по строкам - во первых странно строить новые типы итераторов на базе iostream который сам итератор и понятно что получается сложно местами. has_next можно убрать если проверять поток на окончание.

    Из C# итератора вы выкинули главное его свойство - ленивость(создание итератора не запускает чтение данных)

    С итерацией по директориям вы тоже перемудрили.

    Ну и итераторы это то где как раз уместно оптимизировать производительность вплоть до инструкций.

    В общем тема интересная, но над содержанием и выводами надо критически поработать.


    1. feelamee
      31.08.2024 22:03

      begin() и end() должны возвращать одинаковый тип

      после C++17 нет

      чем C++20 ranges и пользуются


      1. KanuTaH
        31.08.2024 22:03
        +1

        Это скорее для ренджей из C++20, ну и в range-based for тоже будет работать из-за его семантики, но не в "классических" алгоритмах, например std::for_each с этим сентинелом работать не сможет.


  1. upcFrost
    31.08.2024 22:03

    var it = collection.__iter__();
    while (true) {
        try {
            let current = it.__next__();
            ...current...
        }
        catch (StopIteration) {
            break;
        }
    }
    

    Для начала отступы а не скобки. Далее что за var и let, это не жс. Это не питон короче

    А так если нет элементов none

    while (current := next(it, None)) is not None:
        ...
    


    1. alextretyak Автор
      31.08.2024 22:03

      Это не питон короче

      Это псевдокод.
      Или как вы предлагаете следовало поступить?
      Код обхода итератора всегда писать на том языке программирования, к которому он относится?

      Не все знакомы с синтаксисом Python или того же Rust.

      Поэтому я выбрал что-то среднее между C++/C# и JavaScript, т.к. синтаксис Си-подобных языков знаком большинству программистов.


  1. funny_falcon
    31.08.2024 22:03

    Ещё забыли модель итераторов Lua.