Итераторы в Rust

Реализация итераторов в Rust вышла довольно удобная, да и сама коллекция доступных итераторов обширна и вполне сравнима с коллекцией итераторов из библиотеки BOOST.

let mut xs = ~[1, 2, 3];
{
    let it = xs.iter();  // (1)
    //xs.push(4);        // (2)
}


Перед тем как говорить о деталях работы с итераторами, стоит сказать о крайне важном отличие итераторов Rust от итераторов в большинстве других языков программирования. Компилятор Rust, после создания итератора для коллекции 1, заприщает какие-либо модификации коллекции. Благодаря этому, итераторы в Rust никогда не становятся недействительными. При попытке убрать комментарии из строки 2, компилятор выдаст сообщение об ошибке следующего рода:

error: cannot borrow `xs` as mutable because it is also borrowed as immutable

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

let data = [1, 2, 4, 6, 10];
for val in data.iter() {
    println(fmt!("Value: %?", val));
}

Самый простейший вариант использования итератора: обход всех элементов массива. Единственное что тут заслуживает внимания – это новое ключевое слово in, которое должно появиться в составе компилятора версии 0.8, ну а сейчас поддержку такого кода можно обеспечить сборкой компилятора из репозитория.

let data = [1, 2, 4, 6, 10];
for (pos, val) in data.iter().enumerate() {
    println(fmt!("Value: %? with pos: %?", val, pos));
}

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

let data = [1, 2, 4, 6, 10];
let (lower, upper) = data.iter().size_hint();
println(fmt!("Lower bound: %?, upper bound: %?", upper, lower));

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

let data = [0, 1, 1, 2, 3, 5, 8];
let res1: ~[int] = data.iter().map(|&x| x * 2).collect();      // (1)
let res2 = data.iter().map(|&x| x * 2).collect::<~[int]>();    // (2)
//let res3: ~[uint] = data.iter().map(|&x| x * 2).collect();   // (3)
println(fmt!("res1: %?\nres2: %?", res1, res2));

Данные, полученные в результате итерации могут быть собранны в виде массива. Правда, тут есть одно несколько смущающее меня ограничение. Так, тип результат, например массив типа int, должен быть задан явно, либо в качестве типа результирующей переменной 1 или в виде явной инстанциации шаблона 2. При этом, компилятор явно знает какой результат должен получиться в итоге, т.к. если для примера выше изменить тип данных массива с int на uint, то компилятор этого действия не одобрит:

error: expected std::iterator::FromIterator<int,std::iterator::Map<,&int,int,std::vec::VecIterator<,int>>>, but found std::iterator::FromIterator<uint,<V3694>> (expected int but found uint)

Хочется верить, что это прост ошибка компилятора, а не особенность дизайна языка

let data = [1, 2, 4, 6, 10];
let mut it = data.iter().map(|&val| 2 * val);
println(fmt!("transformed values: %?", it.collect::<~[int]>()));
println(fmt!("initial data: %?", data));

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

Более детально об итераторах можно прочитать в заметке Containers and iterators на сайте языка или в документации по модулю iterator.

16 Comments Итераторы в Rust

  1. eao197

    Упс… А сохранить итератор в какой-то структуре данных, получается, невозможно? В плюсах можно было, при желании сделать контейнер из итераторов. Не думаю, что на уровне компилятора такую штуку можно контролировать.

    Reply
    1. Alexander Stavonin

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

      fn iter(self) -> VecIterator<'self, T>

      А итератор строки так:

      fn iter(&self) -> CharIterator<'self>

      И между VecIterator и CharIterator нет ничего общего кроме того, что для обоих типов реализован трэйт Iterator, как следствие, разнородные итераторы ты тоже вместе хранить не сможешь. Но это уже совсем не проблема, на фоне того что массив итераторов, похоже что, не создашь

      Reply
      1. eao197

        Итератор можно рассматривать как аналог указателя. Массив указателей, каждый элемент которого указывает на элемент из какого-то другого массива — это же для C/C++ вполне нормальное дело.

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

        В случае с плюсовым list-ом, ЕМНИП, ты даже можешь использовать этот промежуточный вектор для удаления элементов из исходного list-а.

        PS. А у тебя в блоге что, ответы на комментарии по почте не присылаются?

        Reply
        1. Alexander Stavonin

          Но ведь хранение итератора создает дополнительные неудобства как минимум тем, что от может стать недействительным. И как следствие, всегда надо помнить о том, что у тебя где-то есть коллекция итераторов, которая может “неожиданно” стать не действительной. Мне кажется, концепция блокирования коллекции на изменение до тех пор, пока жив итератор коллекции, идея довольно верная, она, немного, ограничивает возможности, зато оберегает от ночей в отладчике.

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

          Reply
          1. eao197

            Как я говорил, итераторы можно рассматривать как указатели. В этом смысле инвалидация итератора такая же ожидаемая штука, как и инвалидация указателя.

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

            Кроме того, не зря же существуют два типа итераторов: внешние (как в C++) и внутренние. Внутренние, помнится, раньше активно использовались в стандартной библиотеке Eiffel-я. Частично с внутренними итераторами разработчик сталкивается, когда вызывает операции map/inject/fold над коллекциями (например, в Ruby).

            Вот когда внутренний итератор блокирует коллекцию, это мне больше понятно. Хотя здесь, имхо, на compile-time никаких гарантий дать нельзя, все проверки будут выполняться в run-time. Но вот блокировка коллекции внешними итераторами… Это неожиданная идея. Либо к ней нужно привыкнуть, либо она неправильная

          2. Alexander Stavonin

            Вообще, блокировка коллекции при наличии итератора для Rust логичный шаг. Все дело в отслеживании времени жизни переменных на этапе компиляции, которое имеет место в Rust. Собственно, компилятор об это и сказал: уже есть неизменяемый итератор и сделать еще один захват в качестве изменяемого никак нельзя. Если компилятор попытаться обхитрить, и захватить изменяемый итератор mut_iter(), то компилятор скажет что нельзя захватить итератор одного и того же типа дважды
            Вообще, отслеживание времени жизни на этапе компиляции вызывает некоторые неудобства, но потенциальные плюсы, как мне кажется, перевешивают минусы.

          3. eao197

            Ну хорошо. Допустим есть задача пройти по коллекции, собрать ссылки на некоторые ее элементы в отдельном контейнере, затем пройти по этому новому контейнеру.
            В новый контейнер собирать итераторы нельзя. Значит придется собирать ссылки на значения из коллекции. Но если мы сохраним в новом контейнере ссылки на значения, то кто нам помешает изменить потом исходную коллекцию? И, получить невалидные ссылки.

          4. Alexander Stavonin

            Компилятор не позволит тебе менять эти ссылки. Обрати внимание на следующий код:

            let mut xs = ~[1, 2, 3];
            {
                let it = xs.mut_iter();
                xs.push(4);
            }

            И сообщение компилятора не тему того, что он об этом коде думает:

            error: cannot borrow `xs` as mutable more than once at a time

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

          5. eao197

            Мы с тобой, похоже, о разном говорим. Ты мне показываешь, что компилятор не дает изменить коллекцию, когда ты делаешь итерацию по ней. Это я понял. Но что, если в результате первой итерации ты должен сделать вторую коллекцию, состоящую из ссылок на элементы первой коллекции. После того, как ты закончишь первую итерацию, никаких итераторов на первую коллекцию у тебя не останется. Поэтому компилятор не запретит тебе модифицировать ее.

          6. Alexander Stavonin

            Так и коллекцию ссылок тебе компилятор создать не даст, в этом то и дело. Время жизни ссылки будет рассчитывать относительно времени жизни итератора, и как следствие, ссылку, которая живет дольше итератора, ты тоже не создашь.

          7. eao197

            Как-то все это неоднозначно. Нужно бы подождать впечатлений о тех, кто попользуется Rust-ом пару-тройку лет.

          8. Alexander Stavonin

            Да, я с тобой полностью согласен, у меня Rust тоже некоторые опасения вызывает, поглядим на развитие Servio. Но, на данный момент, это единственная потенциальная альтернатива C++ %)

  2. night beast

    согласен с Евгением.
    блочить коллекцию пока есть (видимые?) итераторы как-то не нормально.
    для тех же списков или мапы это совсем лишнее.

    Reply
    1. Alexander Stavonin

      А какие есть еще идеи на тему того, как гарантировать безопасность операций с коллекцией на этапе компиляции? С учетом того, что обеспечение безопасности операций с памятью – одна из основных целей языка, шаг выглядит логичным.
      P.S. ни разу за 12+ лет разработки на плюсах не хранил итераторы, передавал их куда-либо, делал по ним обход, но хранить. ХЗ, видимо авторы Rust тоже такой сценарий использования не рассматривают

      Reply
      1. night beast

        А нужно ли гарантировать безопасность операций с коллекцией на этапе компиляции? Всех проблем все равно не прикроешь, а дополнительного головняка добавится.
        Для упомянутых списков память при вставке не инвалидируется, так зачем ограничивать разработчика.

        Итераторы хранить приходилось.
        Последний раз это было когда понадобилась обертка над стандартным итератором с дополнительной функциональностью.

        PS: за 12 лет часто тебе приходилось сталкиваться с проблемой с итераторами?
        PPS: сам на эту граблю наступал искать было весело но считаю фичу лишней.

        Reply
        1. Alexander Stavonin

          Гарантия безопасности операций с памятью – это одна из основных фич Rust. Поэтому, я думаю, что да, гарантировать безопасность операций с коллекциями надо.
          Проблемы с итераторами бывали, хоть и не часто. В основном от непонимания когда итератор становится недействительным. Поэтому, меня фича только радует, чем меньше возможностей расстрелять память – тем лучше.

          Reply

Leave a Reply to night beast Cancel reply