Перейти к содержимому
Ferris the Rust crabУчебник по Rust

Свои итераторы в Rust

На странице Итераторы ты пользовался итераторами, которые даёт стандартная библиотека: vec.iter(), .map(), .filter(), .sum(). Но можно создавать и свои итераторы. Таймер обратного отсчёта, числа Фибоначчи, страницы отчёта, строки файла в своём формате — всё, что выдаёт значения по одному, может быть итератором.

Хорошая новость: писать нужно всего один метод — next. Все адаптеры — map, filter, take, sum, zip и ещё десятки — Rust даёт тебе даром. Представь автомат с талонами в очереди. Ты делаешь только ту часть, что печатает следующий талон. Очередь, табло и надпись «сейчас обслуживается» работают сами.

Первый итератор: обратный отсчёт

Заголовок раздела «Первый итератор: обратный отсчёт»

Чтобы тип стал итератором, реализуй для него трейт Iterator. Ему нужны две вещи:

  • type Item — какие значения выдаёт итератор (подробнее об ассоциированных типах — в уроке Продвинутые трейты).
  • fn next(&mut self) -> Option<Self::Item> — вернуть Some(значение) для следующего значения или None, когда значений больше нет.
struct Countdown {
    current: u32,
}


impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}


impl Iterator for Countdown {
    type Item = u32;


    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None // закончили
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}


fn main() {
    let mut countdown = Countdown::new(3);


    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());


    for n in Countdown::new(3) {
        println!("{}...", n);
    }
    println!("Пуск!");
}

Вывод:

Some(3)
Some(2)
Some(1)
None
None
3...
2...
1...
Пуск!
▶ Попробуй сам

На что стоит обратить внимание:

  • next принимает &mut self, потому что меняет итератор. Структура помнит, где она находится (current), и каждый вызов сдвигает её вперёд. Поэтому countdown должен быть объявлен через let mut.
  • Вернуть None значит сказать «я закончил». Цикл for вызывает next снова и снова и останавливается на первом None.
  • Наш обратный отсчёт после окончания продолжает возвращать None. Это вежливо, но трейт этого не требует — некоторые итераторы могут начать заново. Если нужна гарантия, вызови .fuse() у любого итератора.

Бесконечный итератор: Фибоначчи

Заголовок раздела «Бесконечный итератор: Фибоначчи»

Итератор не обязан заканчиваться. Последовательность Фибоначчи (0, 1, 1, 2, 3, 5, 8, …) бесконечна: каждое число — сумма двух предыдущих. Итератору нужно лишь помнить два последних числа:

struct Fibonacci {
    current: u64,
    next: u64,
}


impl Fibonacci {
    fn new() -> Self {
        Fibonacci { current: 0, next: 1 }
    }
}


impl Iterator for Fibonacci {
    type Item = u64;


    fn next(&mut self) -> Option<u64> {
        let value = self.current;
        // checked_add возвращает None при переполнении, а `?` передаёт этот None дальше,
        // так что итератор заканчивается, а не падает, когда числа становятся слишком большими.
        let new_next = self.current.checked_add(self.next)?;
        self.current = self.next;
        self.next = new_next;
        Some(value)
    }
}


fn main() {
    let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("{:?}", first_ten);
}

Вывод:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
▶ Попробуй сам

Всё решает .take(10). Без него collect() попытался бы собрать всю последовательность. Бесконечный итератор всегда ограничивай чем-нибудь вроде take, take_while или find.

Все адаптеры — даром

Заголовок раздела «Все адаптеры — даром»

А вот самое приятное. У трейта Iterator около 75 методов, и у всех, кроме next, есть реализации по умолчанию, построенные на next. Так что как только ты написал next, твой тип может пользоваться всеми ими:

struct Countdown {
    current: u32,
}


impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}


impl Iterator for Countdown {
    type Item = u32;


    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}


fn main() {
    let total: u32 = Countdown::new(5).sum();
    println!("Сумма: {}", total);


    let evens: Vec<u32> = Countdown::new(10).filter(|n| n % 2 == 0).collect();
    println!("Чётные: {:?}", evens);


    let labels: Vec<String> = Countdown::new(3).map(|n| format!("T-{}", n)).collect();
    println!("Метки: {:?}", labels);


    let multiple = Countdown::new(100).find(|n| n % 7 == 0);
    println!("Первое кратное 7: {:?}", multiple);


    let pairs: Vec<(u32, char)> = Countdown::new(3).zip(['a', 'b', 'c']).collect();
    println!("Пары: {:?}", pairs);
}

Вывод:

Сумма: 15
Чётные: [10, 8, 6, 4, 2]
Метки: ["T-3", "T-2", "T-1"]
Первое кратное 7: Some(98)
Пары: [(3, 'a'), (2, 'b'), (1, 'c')]
▶ Попробуй сам

Отличный пример того, почему трейты в Rust так полезны. На входе — один маленький метод, на выходе — огромный набор инструментов.

Итераторы ленивые

Заголовок раздела «Итераторы ленивые»

Адаптеры вроде map и take сами ничего не делают. Они просто строят «план». Работа начинается, только когда что-то потребляет итератор: цикл for, collect, sum и так далее. Докажем это итератором, который печатает сообщение при каждом вызове next:

struct Noisy {
    n: u32,
}


impl Iterator for Noisy {
    type Item = u32;


    fn next(&mut self) -> Option<u32> {
        self.n += 1;
        println!("  вызван next(), отдаёт {}", self.n);
        Some(self.n)
    }
}


fn main() {
    println!("Строим цепочку...");
    let chain = Noisy { n: 0 }.map(|x| x * 10).take(3);
    println!("Пока ничего не выполнялось. Теперь потребляем:");


    for value in chain {
        println!("получено {}", value);
    }
    println!("Готово");
}

Вывод:

Строим цепочку...
Пока ничего не выполнялось. Теперь потребляем:
  вызван next(), отдаёт 1
получено 10
  вызван next(), отдаёт 2
получено 20
  вызван next(), отдаёт 3
получено 30
Готово
▶ Попробуй сам

Здесь два урока. Во-первых, построение цепочки ничего не напечатало — ни одного вызова next(). Во-вторых, значения проходят по одному: один next, один map, одно «получено», и только потом следующее значение. Никакого скрытого списка посередине нет. И хотя Noisy никогда не заканчивается, программа завершается: после трёх элементов take(3) просто перестаёт спрашивать.

Своя коллекция в циклах for

Заголовок раздела «Своя коллекция в циклах for»

До сих пор наши структуры сами были итераторами. Но часто у тебя есть коллекция — структура, которая хранит элементы, — и хочется, чтобы по ней можно было пройти циклом, как по Vec. Для этого реализуют IntoIterator. Именно этот трейт использует цикл for: for x in thing на самом деле вызывает thing.into_iter().

Коллекции обычно предлагают три способа обхода, и полезно увидеть их на своём типе:

Ты пишешь Метод за этим Каждый элемент — это Коллекция после цикла
for s in &playlist playlist.iter() &String (только чтение) по-прежнему доступна
for s in &mut playlist playlist.iter_mut() &mut String (можно менять) по-прежнему доступна
for s in playlist playlist.into_iter() String (во владении) перемещена, её больше нет

Вот Playlist, который поддерживает все три способа. Наша структура хранит песни в Vec, поэтому можно отдавать собственные итераторы Vec, а не писать новые.

Названия песен здесь английские: мы переводим их в верхний регистр и ищем самое длинное через .len(), а она считает байты.

struct Playlist {
    songs: Vec<String>,
}


impl Playlist {
    fn iter(&self) -> std::slice::Iter<'_, String> {
        self.songs.iter()
    }


    fn iter_mut(&mut self) -> std::slice::IterMut<'_, String> {
        self.songs.iter_mut()
    }
}


// Чтобы работало `for song in &playlist`
impl<'a> IntoIterator for &'a Playlist {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;


    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}


// Чтобы работало `for song in &mut playlist`
impl<'a> IntoIterator for &'a mut Playlist {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;


    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}


// Чтобы работало `for song in playlist` (плейлист при этом расходуется)
impl IntoIterator for Playlist {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;


    fn into_iter(self) -> Self::IntoIter {
        self.songs.into_iter()
    }
}


fn main() {
    let mut playlist = Playlist {
        songs: vec![String::from("intro"), String::from("main theme"), String::from("outro")],
    };


    for song in &playlist {
        println!("Читаем: {}", song);
    }


    for song in &mut playlist {
        *song = song.to_uppercase();
    }


    println!("Самая длинная: {:?}", playlist.iter().max_by_key(|s| s.len()));


    for song in playlist {
        println!("Забираем: {}", song);
    }
    // Последний цикл переместил `playlist`, поэтому здесь его использовать нельзя.
}

Вывод:

Читаем: intro
Читаем: main theme
Читаем: outro
Самая длинная: Some("MAIN THEME")
Забираем: INTRO
Забираем: MAIN THEME
Забираем: OUTRO
▶ Попробуй сам

Строк много, но все impl устроены одинаково: скажи, что такое Item, скажи, какой тип итератора возвращаешь (IntoIter), и верни его. 'a — это время жизни: оно говорит, что «заимствованные элементы живут столько же, сколько заимствованный плейлист». Этот шаблон можно копировать почти для любой коллекции, которая оборачивает Vec.

Обход с конца и известная длина

Заголовок раздела «Обход с конца и известная длина»

Стоит знать ещё два трейта. Нужны они нечасто, но от них зависят адаптеры вроде .rev() и .len():

  • DoubleEndedIterator добавляет next_back, который берёт элементы с конца. Он открывает .rev().
  • ExactSizeIterator обещает, что итератор точно знает, сколько элементов осталось. Он открывает .len(). Кроме того, в Iterator ты даёшь точный size_hint.
// Выдаёт low, low+1, ..., high-1 (как диапазон low..high)
struct Between {
    low: u32,
    high: u32,
}


impl Iterator for Between {
    type Item = u32;


    fn next(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        let value = self.low;
        self.low += 1;
        Some(value)
    }


    fn size_hint(&self) -> (usize, Option<usize>) {
        let left = self.high.saturating_sub(self.low) as usize;
        (left, Some(left))
    }
}


impl DoubleEndedIterator for Between {
    fn next_back(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        self.high -= 1;
        Some(self.high)
    }
}


impl ExactSizeIterator for Between {}


fn main() {
    let backwards: Vec<u32> = Between { low: 1, high: 6 }.rev().collect();
    println!("{:?}", backwards);


    let mut both_ends = Between { low: 1, high: 6 };
    println!("спереди {:?}, сзади {:?}", both_ends.next(), both_ends.next_back());
    println!("осталось: {}", both_ends.len());
}

Вывод:

[5, 4, 3, 2, 1]
спереди Some(1), сзади Some(5)
осталось: 3
▶ Попробуй сам

Два конца движутся навстречу друг другу, и итератор заканчивается, когда они встречаются. impl ExactSizeIterator for Between {} пустой: len() использует size_hint, который ты уже написал.

Короткие пути: from_fn и successors

Заголовок раздела «Короткие пути: from_fn и successors»

Структура с impl отлично подходит для итераторов, которые используются многократно. Для быстрого одноразового итератора в std::iter есть два помощника:

  • iter::from_fn(closure) вызывает твоё замыкание каждый раз, когда нужно значение. Замыкание возвращает Some(значение) или None, ровно как next.
  • iter::successors(first, closure) начинает с первого значения, а замыкание вычисляет каждое следующее из предыдущего. Возврат None всё заканчивает.
use std::iter;


fn main() {
    // from_fn: замыкание хранит своё состояние (count)
    let mut count = 3;
    let countdown: Vec<u32> = iter::from_fn(|| {
        if count == 0 {
            None
        } else {
            count -= 1;
            Some(count + 1)
        }
    })
    .collect();
    println!("{:?}", countdown);


    // successors: каждое значение вычисляется из предыдущего
    let powers: Vec<u32> = iter::successors(Some(1u32), |&n| n.checked_mul(10)).collect();
    println!("{:?}", powers);


    // Фибоначчи в одну строку: несём два последних числа парой
    let fib: Vec<u64> = iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
        .take(10)
        .collect();
    println!("{:?}", fib);
}

Вывод:

[3, 2, 1]
[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
▶ Попробуй сам

powers останавливается сам: следующая степень десяти, 10 000 000 000, не помещается в u32, поэтому checked_mul возвращает None, и итератор заканчивается. Хорошее правило: используй эти короткие пути внутри одной функции, а именованную структуру пиши, когда итератор нужно создавать из другого кода или когда у него много состояния.

Частые ошибки

Заголовок раздела «Частые ошибки»

Забытый mut, когда сам вызываешь next. next меняет итератор, поэтому переменная должна быть изменяемой:

let countdown = Countdown { current: 3 };
println!("{:?}", countdown.next());
error[E0596]: cannot borrow `countdown` as mutable, as it is not declared as mutable
  --> src/main.rs:20:22
   |
20 |     println!("{:?}", countdown.next());
   |                      ^^^^^^^^^ cannot borrow as mutable
   |
help: consider changing this to be mutable
   |
19 |     let mut countdown = Countdown { current: 3 };
   |         +++

Компилятор говорит, что countdown нельзя заимствовать как изменяемый, потому что он не объявлен изменяемым. Добавь mut. (Циклу for он не нужен: цикл сам забирает итератор и обо всём заботится.)

Забытый type Item. Трейту нужно знать, что ты выдаёшь:

error[E0046]: not all trait items implemented, missing: `Item`
 --> src/main.rs:5:1
  |
5 | impl Iterator for Countdown {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `Item` in implementation
  |
  = help: implement the missing item: `type Item = /* Type */;`

Компилятор сообщает, что в реализации не хватает Item. Добавь внутрь impl строку type Item = u32; (или тот тип, который выдаёт твой итератор).

collect бесконечного итератора. Fibonacci::new().collect::<Vec<_>>() (без take) прекрасно компилируется, но так и не завершается с пользой: он работает, пока числа не переполнятся, или вечно, если твой next никогда не возвращает None. Компилятор этого не поймает. Если итератор может оказаться бесконечным, всегда добавляй take, take_while или find, прежде чем его потреблять.

Итоги

Заголовок раздела «Итоги»
  • Реализуй Iterator через type Item и fn next(&mut self) -> Option<Self::Item>. Когда закончил, возвращай None.
  • Как только есть next, ты даром получаешь map, filter, take, sum, zip и ещё десятки методов.
  • Итераторы ленивые: ничего не происходит, пока их не потребит цикл for, collect, sum и т. п., и элементы проходят по одному.
  • Реализуй IntoIterator для &MyType, &mut MyType и MyType, чтобы поддержать циклы for, которые заимствуют, заимствуют изменяемо или забирают коллекцию.
  • DoubleEndedIterator включает .rev(); ExactSizeIterator включает .len().
  • Для быстрых одноразовых итераторов используй std::iter::from_fn или std::iter::successors.

Проверь себя

Заголовок раздела «Проверь себя»

Проверь себя

1. Что должен вернуть next, когда у итератора больше нет элементов?

2. Ты реализовал только next. Можно ли вызвать у итератора .map() и .sum()?

3. Когда в примере с ленивыми вычислениями впервые вызывается next()?

4. Какая реализация заставляет работать for song in &playlist?

5. Какой трейт нужен, чтобы у твоего итератора работал .rev()?

Результат: 0 / 5

Что почитать

Заголовок раздела «Что почитать»