11. Итераторы

Трейт Iterator

В основе всех итераторов в Rust лежит один трейт с единственным обязательным методом. Всё остальное — map, filter, fold, collect и десятки других — реализовано как методы по умолчанию поверх next(). Это принципиально отличается от Go, где итерация по range — языковая конструкция, а не пользовательский трейт.

pub trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;

    // Десятки методов по умолчанию: map, filter, fold, take, skip...
    fn map<B, F>(self, f: F) -> Map<Self, F>
    where
        Self: Sized,
        F: FnMut(Self::Item) -> B,
    { /* ... */ }
}

Ассоциированный тип Item фиксирует, что именно возвращает итератор — в отличие от дженерика, для одного типа может существовать только одна реализация Iterator (но можно иметь несколько итераторов над одной коллекцией: iter(), iter_mut(), into_iter()).

• Iterator — трейт с next() -> Option<Item>, всё остальное строится поверх него
• Итератор конечен, когда next() возвращает None — но не обязан быть конечным (например, 0.. бесконечен)

IntoIterator и три способа итерации

for в Rust — синтаксический сахар над трейтом IntoIterator. Выражение for x in collection компилируется в вызов collection.into_iter() и цикл вокруг next(). У большинства коллекций есть три метода, дающих разные виды доступа к элементам.

let v = vec![1, 2, 3];

for x in &v {          // v.iter() → Item = &i32
    println!("{x}");
}
for x in &mut v {      // v.iter_mut() → Item = &mut i32
    *x += 1;
}
for x in v {           // v.into_iter() → Item = i32, забирает владение
    println!("{x}");
}
// v больше недоступен: into_iter() переместил его

Ленивые адаптеры

Методы вроде map, filter, take, skip, zip, enumerate, chain — это адаптеры: они оборачивают исходный итератор в новую структуру, но не выполняют вычислений сами по себе. Итерация ленива — ничего не происходит, пока итератор не будет "потреблён" терминальным методом (collect, for, sum, count и т.д.).

let v = vec![1, 2, 3, 4, 5];

let iter = v.iter()
    .map(|x| { println!("map: {x}"); x * 2 })
    .filter(|x| x % 3 == 0);
// Ничего не напечаталось! Адаптеры только строят цепочку.

let result: Vec<_> = iter.collect();
// А вот теперь "map: 1" .. "map: 5" напечатались по одному —
// значения текут по конвейеру поэлементно, а не батчами.

Это и есть zero-cost abstraction: цепочка адаптеров компилируется в код, эквивалентный ручному циклу с проверками — компилятор инлайнит вызовы next() и обычно устраняет промежуточные аллокации полностью.

// Эти два варианта дают идентичный машинный код после оптимизации:
let sum: i32 = (0..1000).filter(|x| x % 2 == 0).sum();

let mut sum2 = 0;
for x in 0..1000 {
    if x % 2 == 0 { sum2 += x; }
}

Терминальные методы: collect, fold, reduce

collect — самый универсальный терминальный метод: он строит любой тип, реализующий FromIterator. Целевой тип обычно выводится из контекста, но при неоднозначности нужна аннотация — либо через переменную, либо через turbofish ::<>.

let doubled: Vec<i32> = (1..5).map(|x| x * 2).collect();

// turbofish — когда тип нельзя вывести из контекста
let set = (1..5).collect::<HashSet<i32>>();

// collect в Result — прерывается на первой ошибке!
let parsed: Result<Vec<i32>, _> = "1,2,x,4"
    .split(',')
    .map(|s| s.parse::<i32>())
    .collect();
// Err(ParseIntError) — как только встретился "x"

// fold — накопитель с явным начальным значением
let total = (1..=5).fold(0, |acc, x| acc + x);

// reduce — как fold, но начальное значение — первый элемент
let max = vec![3, 7, 2].into_iter().reduce(|a, b| a.max(b));

Кастомные итераторы

Чтобы сделать тип итерируемым, достаточно реализовать next() — всё остальное (более 70 методов) достаётся бесплатно через default-реализации трейта.

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

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let new_next = self.curr + self.next;
        self.curr = self.next;
        self.next = new_next;
        Some(self.curr)   // бесконечный итератор — никогда не вернёт None
    }
}

fn fibonacci() -> Fibonacci {
    Fibonacci { curr: 0, next: 1 }
}

let first_ten: Vec<u64> = fibonacci().take(10).collect();

Чтобы кастомная коллекция поддерживала for, реализуйте IntoIterator — обычно делегируя работу к внутреннему Iterator:

struct Grid { cells: Vec<i32> }

impl IntoIterator for Grid {
    type Item = i32;
    type IntoIter = std::vec::IntoIter<i32>;

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

Специализированные трейты и производительность

Дополнительные трейты позволяют оптимизировать конкретные операции без потери общности API.

• DoubleEndedIterator — добавляет next_back(), позволяет итерировать с конца (.rev())
• ExactSizeIterator — гарантирует len() за O(1), нужен для точного резервирования памяти в collect
• FusedIterator — гарантирует, что после первого None итератор всегда будет возвращать None (компилятор может убрать лишние проверки)

fn size_hint(&self) -> (usize, Option<usize>) {
    // (нижняя граница, верхняя граница) — collect использует это
    // для предварительного резервирования памяти в Vec::with_capacity
    (self.remaining, Some(self.remaining))
}

Частые ловушки

// 1. Итератор нужно "потребить" — сам по себе он ничего не делает
(0..5).map(|x| println!("{x}"));  // предупреждение: unused iterator, ничего не печатает
(0..5).for_each(|x| println!("{x}")); // корректно — for_each терминальный

// 2. collect::<Vec<_>>() посреди цепочки убивает лень и аллоцирует лишнее
let bad: Vec<_> = data.iter().collect();       // лишняя аллокация
let sum: i32 = bad.iter().sum();

// лучше — одна цепочка без промежуточного Vec
let sum: i32 = data.iter().sum();

// 3. clone() внутри map, когда достаточно ссылки — лишние аллокации
strings.iter().map(|s| s.clone()).collect::<Vec<String>>();