Rust: for и итераторы

в 12:58, , рубрики: for loop, Rust, итераторы, перевод, Программирование, системное программирование, циклы

(предыдущая статья)
Rust: for и итераторы - 1
В данной статье мы обсудим for циклы, а так же родственные понятия итераторов и «итерируемых объектов».

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

Основы

В Расте синтаксис for цикла практически по-спартански немногословен:

let v = vec!["1", "2", "3"];
for x in v {
    println!("{}", x);
}

(Вариант цикла for через двойную точку с запятой отсутствует в Расте как явление, так же как и в Питоне мы либо можем итерировать по некоторому диапазону, либо использовать while или loop для более сложных случаев)

Ожидаемо код выше напечатает три строчки с 1, 2, 3. Возможно менее очевидным является тот факт, что вектор v был перемещён внутрь цикла во время его исполнения. Попытка использовать этот вектор после цикла выдаст ошибку:

<anon>:6:22: 6:23 error: use of moved value: `v` [E0382]
<anon>:4         println!("{}", x);
<anon>:5     }
<anon>:6     println!("{:?}", v);
                              ^

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

Но не привыкнув полностью к правилам перемещения и заимствования данный факт всё-равно может оказаться для вас сюрпризом, т.к. по большей части перемещение ассоциируется с вызовом функций и их контекстом. В большинстве случаев, для упрощения понимания, вы можете считать for цикл выше аналогичным функции for_each:

for_each(v, |x| println!("{}", x));

Данное представление так же даёт подсказку как нам избежать перемещения значения внутрь цикла. Вместо того что бы передавать сам вектор мы можем передать лишь ссылку на него:

for_each_ref(&v, |x| println!("{}", x));

Переведя данный код обратно в форму цикла:

 for x in &v {
    println!("{}", x);
}
println!("{:?}", v);

Мы избавимся от ошибки компилятора.

Итераторы и «итерируемые объекты»

Важно отметить, что добавленный амперсанд (&) ни в коем случае не является частью синтаксиса цикла for. Мы просто поменяли тот объект по которому мы итерируем, вместо Vec<T>, непосредственно вектора, мы передаём &Vec<T>, неизменяемую (иммутабельную) ссылку на него. Последствием этого является смена типа x с T на &T, т.е. теперь это ссылка на элемент. (это никак не повлияло на тело цикла благодаря наличию "преобразования при разыменовании")

Таким образом получается что Vec<T> и &Vec<T>, оба являются «итерируемыми объектами». Обычным способом реализовать такое для языков программирования является введение особого объекта — «итератора».

Итератор отслеживает на какой элемент он указывает в данный момент и поддерживает как минимум следующие операции:

  1. Получение текущего элемента
  2. Перемещение к следующему элементу
  3. Уведомление о том, что элементы закончились

Некоторые языки предоставляют различные итераторы для каждой из этой задач, но в Расте было решено объединить их в один. Посмотрев на документацию для трейта Iterator вы увидите, что для того что бы удовлетворить ему реализации достаточно иметь один метод next.

Убираем синтаксический сахар

Но как именно создаются объекты-итераторы из итерируемых объектов?

В типичной для Раста манере данная задача делегирована другому трейту, именуемому IntoIterator:

// (упрощено)
trait IntoIterator {
    fn into_iter(self) -> Iterator;
}

Уникальной чертой Раста является то, что into_iter, единственный метод данного трейта, не только создаёт итератор из коллекции, но и по сути поглощает исходную коллекцию, оставляя полученный итератор единственным способом получения доступа к элементам коллекции. (Из-за чего мы можем это утверждать? Всё дело в том, что into_iter получает в качестве аргумента self, а не &self или &mut self, что означает что владение объектом передаётся во внутрь этого метода)

(примечание переводчика: здесь и далее автор не рассматривает подробно разницу между методами коллекций into_iter, iter и iter_mut для создания итераторов, которая заключается в том, что первый перемещает коллекцию вовнутрь себя, а второй иммутабельно заимствует, а значит итерация проходит по иммутабельным ссылкам элементам, третий же заимствует мутабельно, позволяя тем самым во время итерации менять элементы коллекции)

Подобное поведение защищает нас от весьма распространённой ошибки именуемой инвалидацией итератора, которая вероятно достаточно хорошо известна программистам на C++. Т.к. коллекция по сути «сконвертирована» в итератор, то становится невозможным следующее:

  1. Существование более чем одного итератора указывающего на коллекцию
  2. Изменение коллекции пока один из итераторов находится в области видимости

Не звучат ли для вас знакомо все эти «перемещения» и «заимствоания»? Ранее я отметил, что итерируя по вектору в for цикле мы по сути перемещаем его «внутрь цикла».

Как вы можете уже догадаться во время итерации по вектору мы на самом деле вызываем для этого вектора IntoIterator::into_iter, получая на его выходе итератор. Вызывая next в каждой итерации мы продолжаем двигаться по циклу пока не получим None.

Таким образом, цикл:

for x in v {
    // тело цикла
}

В сущности просто синтаксический сахар для следующего выражения:

let mut iter = IntoIterator::into_iter(v);
loop {
    match iter.next() {
        Some(x) => {
            // тело цикла
        },
        None => break,
    }
}

Вы можете хорошо видеть, что v нельзя использовать не только после того как цикл закончится, но даже до того как он начнётся. Это произошло т.к. мы переместили вектор внутрь итератора iter посредством метода into_iter трейта… IntoIterator!

Просто, не правда ли? :)

Цикл for является синтаксическим сахаром для вызова IntoIterator::into_iter с последующим неоднократным вызовом Iterator::next.

Амперсанд

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

for x in &v {
    // тело цикла
}

(прим. перев.: эквивалентно for x in v.iter() {...})

При этом всё о чём мы говорили выше применяется и здесь, вплоть до раскрытия синтаксического сахара. Метод into_iter вызывается так же как и раньше, с одним различием, вместо вектора он получает ссылку на него:

// (упрощено)
impl IntoIterator for &Vec<T> {
    fn into_iter(self) -> Iterator<Item=&T> { ... }
}

Таким образом итератор на выходе будет выдавать ссылки на элементы вектора (&T), а не сами элементы (T). И т.к. self выше это тоже ссылка, коллекция никуда не перемещается, благодаря чему мы можем спокойно обращаться к ней после окончания цикла.

Тоже самое и для изменяемых ссылок:

for x in &mut v {
    // тело цикла
}

(прим. перев.: эквивалентно for x in v.iter_mut() {...})

С той лишь разницей что теперь into_iter вызывается для &mut Vec<T>. Соответственно результат вида Iterator<Item=&mut T> позволяет нам модифицировать элементы коллекции.

Для поддержки этих двух случаев нам не потребовалось никакой дополнительной поддержки компилятора, т.к. всё уже покрыто одним и тем же трейтом.

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

Что насчёт метода iter?

До сих пор мы говорили только об циклах for, представляющих весьма императивный стиль вычислений.

Если же вы более склонны к функциональному программированию, вы возможно видели и писали различные конструкции, комбинирующие методы подобные таким:

let doubled_odds: Vec<_> = numbers.iter()
    .filter(|&x| x % 2 != 0).map(|&x| x * 2).collect();

Методы наподобии map и filter называются адаптерами итераторов, и все они определяются для трейта Iterator. Они не только весьма многочисленны и выразительны, но и могут поставляться сторонними крейтами.

Для того что бы воспользоваться преимуществами адаптеров нам необходимо сначала получить итератор. Мы знаем, что циклы обычно получают его через into_iter, поэтому в принципе мы можем использовать тот же подход и здесь:

let doubled_odds: Vec<_> = IntoIterator::into_iter(&numbers)
    .filter(|&x| x % 2 != 0).map(|&x| x * 2).collect();

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

v.iter() не более чем сокращение для IntoIterator::into_iter(&v).

Как насчёт обоих?

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

Таким образом, выбор того или иного подхода не более чем вопрос стиля и привычки. Иногда верным решением будет смешать оба подхода, что Раст позволяет сделать без проблем:

fn print_prime_numbers_upto(n: i32) {
    println!("Prime numbers lower than {}:", n);
    for x in (2..n).filter(|&i| is_prime(i)) {
        println!("{}", x);
    }
}

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

Сами итераторы так же являются «итерируемыми объектами», посредством «прозрачной» реализации трейта IntoIterator::into_iter.

В заключение

Если вы хотите узнать больше информации об итераторах и циклах лучшим источником для вас будет официальная документация. И хотя овладение всеми адаптерами итераторов ни в коем случае необязательно для написания эффективного кода на Расте, весьма вероятно внимательный просмотр документации для метода collect и связанного с ним трейта FromIterator окажется весьма полезным для вас.

Автор: newpavlov

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js