Коллекции и итераторы: ленивость, адаптеры, эффективность

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

Задача. Есть лог на 40 гигабайт. Нужна сумма длительностей запросов с кодом 500, но только для первых десяти тысяч таких. Требования: не грузить файл в память, не строить промежуточных массивов, остановиться сразу по достижении лимита — и всё это одним читаемым выражением.

use std::io::{BufRead, BufReader};
use std::fs::File;

fn main() -> std::io::Result<()> {
    let total: u64 = BufReader::new(File::open("access.log")?)
        .lines()                                   // итератор по строкам, файл читается порциями
        .map_while(Result::ok)                     // обрываемся на первой ошибке ввода-вывода
        .filter(|line| line.contains(" 500 "))     // фильтр без единой аллокации
        .filter_map(|line| parse_duration(&line))  // разбор и отбрасывание мусора за один шаг
        .take(10_000)                              // после 10 000 совпадений чтение прекращается
        .sum();

    println!("суммарная длительность: {total} мкс");
    Ok(())
}

fn parse_duration(line: &str) -> Option<u64> {
    line.rsplit(' ').next()?.parse().ok()          // последнее поле строки, если это число
}

Пиковая память — буфер BufReader (8 КиБ) плюс самая длинная строка. В машинном коде это один цикл: ни виртуальных вызовов, ни промежуточных векторов, ни сборки мусора. То же выражение на Python создаст объект-генератор в куче и на каждый элемент сделает несколько вызовов интерпретатора; на Java Stream API потянет цепочку Spliterator с мегаморфными вызовами, которые JIT инлайнит не всегда. Понять, почему у Rust получается иначе, — цель этой статьи.

Итератор — это машина состояний, а не коллекция

Слово «итератор» в разных языках означает разное. В Rust это любой тип, реализующий один трейт с одним обязательным методом:

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // ...и ещё около 75 методов с реализациями по умолчанию, все выражены через next()
}

Всё. Никакой пары «начало/конец», никакого внутреннего курсора, который можно инвалидировать. Итератор — это изменяемое состояние плюс функция «дай следующее». Option в возвращаемом типе делает исчерпание частью типа: забыть проверить конец нельзя, компилятор заставит разобрать Option.

Цикл for — сахар ровно над этим:

let v = vec![10, 20, 30];

for x in &v { println!("{x}"); }                  // то, что вы пишете

let mut it = IntoIterator::into_iter(&v);         // то, во что это разворачивается
while let Some(x) = it.next() { println!("{x}"); }

Ключевой момент: адаптеры не выполняют работу, они строят тип. v.iter().filter(f).map(g) не обходит вектор — он конструирует значение типа Map<Filter<slice::Iter<'_, i32>, F>, G>, где F и G — анонимные типы замыканий. Оно целиком лежит на стеке, размер известен на этапе компиляции, и в нём нет ни одного указателя на функцию: Map::next знает статически, какое замыкание вызывать, поэтому вызов встраивается.

Такая модель называется внешней итерацией (pull): потребитель тянет значения. Обратная — push, когда коллекция сама вызывает вашу функцию на каждом элементе (forEach в JS, Enum.each в Elixir). У pull два преимущества: её можно остановить в любой момент (take, find, ?) и синхронизировать с другим источником (zip). Цена — состояние приходится хранить явно, поэтому в Rust так тяжело даётся асинхронная итерация, к которой вернёмся в конце. Общая теория ленивых последовательностей — в «Ленивость и потоки».

Важная деталь: Filter крутит свой собственный цикл внутри одного вызова next(). Отброшенные элементы никогда не поднимаются вверх по цепочке — поэтому filter дешевле, чем «сначала собрать, потом отсеять».

Ленивость и её честная цена

Ленивость — не украшение, а следствие устройства. Пока никто не вызвал next(), не исполнено ничего. На этом обжигаются в первый день:

let v = vec![1, 2, 3];
v.iter().map(|x| println!("вижу {x}"));   // не печатает НИЧЕГО

Компилятор здесь на вашей стороне — трейт Iterator помечен #[must_use]:

warning: unused `Map` that must be used
 --> src/main.rs:3:5
  |
3 |     v.iter().map(|x| println!("вижу {x}"));
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: iterators are lazy and do nothing unless consumed
  = note: `#[warn(unused_must_use)]` on by default
help: use `let _ = ...` to ignore the resulting value

Строку iterators are lazy and do nothing unless consumed стоит запомнить дословно. Правильный вариант — обычный for, потому что побочные эффекты в map — плохой стиль.

Вторая грань ленивости: порядок исполнения не совпадает с порядком чтения кода. a.map(f).filter(p) не значит «применить f ко всем, потом отфильтровать»: для каждого элемента сначала работает f, потом p. Если f дорогая, а p отбрасывает 99% — переставьте их. Компилятор такую перестановку не сделает: он не знает, что f чистая.

Три способа взять итератор — и первая настоящая ошибка

Форма for x in ... выбирает вариант через IntoIterator, и вот тут случается классика:

let names = vec![String::from("аня"), String::from("боря")];
for n in names { println!("{n}"); }
println!("всего: {}", names.len());   // ошибка

error[E0382]: borrow of moved value: `names`
 --> src/main.rs:6:27
  |
2 |     let names = vec![String::from("аня"), String::from("боря")];
  |         ----- move occurs because `names` has type `Vec<String>`,
  |               which does not implement the `Copy` trait
3 |     for n in names {
  |              ----- `names` moved due to this implicit call to `.into_iter()`
...
6 |     println!("всего: {}", names.len());
  |                           ^^^^^^^^^^^ value borrowed here after move
  |
note: `into_iter` takes ownership of the receiver `self`, which moves `names`
help: consider iterating over a slice of the `Vec<String>`'s content to avoid
      moving into the `for` loop
  |
3 |     for n in &names {
  |              +

Это образец того, как надо читать rustc: сообщение объясняет почему (for неявно вызвал into_iter), где именно, и даёт готовую правку — один символ &. Правило на всю жизнь: for x in v съедает v, for x in &v — нет. Если элементы нужны по значению, а коллекцию хочется сохранить — iter().cloned(), copied() для Copy-типов или drain(..).

Историческая грабля: до Rust 1.53 у [T; N] не было IntoIterator по значению, и arr.into_iter() из-за автоматического разыменования давало &T. В редакции 2021 массивы отдают значения, в 2015/2018 старое поведение сохранено ради совместимости — если старый код ведёт себя странно, проверьте edition в Cargo.toml.

Карта коллекций: выбор по задаче

Стандартная библиотека даёт восемь коллекций; в 90% кода используются две. Документация модуля std::collections открывается разделом «Which collection should you use?» — редкий случай, когда доки читаются как учебник.

* Амортизированно: изредка происходит реаллокация за O(n). Полный разбор самих структур — в треке data-structures.

Про LinkedList — прямо. В Rust он бесполезнее, чем где-либо. Его теоретическое преимущество (O(1) вставка в середину) требует курсора, а стабильного API курсоров нет. При этом каждый элемент — отдельная аллокация, обход прыгает по памяти и убивает предвыборку кеша: разница с Vec на реальных данных достигает порядка («Кеш и локальность»). Если список всё же нужен — читайте «Learn Rust With Entirely Too Many Linked Lists»: лучший текст о том, почему списки и borrow checker плохо дружат, и заодно курс по Box, Rc, RefCell и unsafe.

Vec: рост, ёмкость и почему реаллокация — дело borrow checker

Vec<T> — три машинных слова: указатель, длина, ёмкость. Данные в куче, одним непрерывным блоком.

let mut v: Vec<i32> = Vec::new();
println!("{} {}", v.len(), v.capacity());   // 0 0 — Vec::new не аллоцирует вообще
for i in 0..9 { v.push(i); print!("{} ", v.capacity()); }
// 4 4 4 4 8 8 8 8 16 — ёмкость удваивается

Удвоение даёт амортизированное O(1) на push: суммарная работа по копированию для n вставок ограничена 2n. Конкретные пороги языком не зафиксированы и зависят от размера элемента — полагаться на числа нельзя, на асимптотику можно.

Реаллокация — это realloc от аллокатора со всеми вытекающими: копирование блока, запрос страниц у ядра, промахи кеша (механика — в «Динамическая память» и «Управление памятью»). Если размер известен — скажите об этом: Vec::with_capacity(n) плюс extend вместо push в цикле.

Главное следствие для модели языка: реаллокация перемещает данные, а значит любая ссылка внутрь вектора становится висячей. В C++ это UB, который проявится через месяц в проде. В Rust — ошибка компиляции:

let mut v = vec![1, 2, 3];
for x in &v {
    if *x == 2 { v.push(99); }
}

error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> src/main.rs:5:13
  |
3 |     for x in &v {
  |              --
  |              |
  |              immutable borrow occurs here
  |              immutable borrow later used here
4 |         if *x == 2 {
5 |             v.push(99);
  |             ^^^^^^^^^^ mutable borrow occurs here

Это не бюрократия, а инвалидация итератора, поймана за долю секунды вместо ночи с отладчиком. Инструменты вместо борьбы:

v.retain(|x| x % 2 == 0);                 // удалить по предикату: один проход на месте, O(n)
for x in v.iter_mut() { *x *= 10; }       // изменить все элементы на месте
let taken: Vec<i32> = v.drain(..).collect();  // забрать по значению, оставив вектор пустым

Отдельно: v.remove(0) в цикле — это O(n²), каждый вызов сдвигает весь хвост. Классическая «очередь на векторе». Порядок не важен — swap_remove за O(1); важен и нужна очередь — VecDeque.

HashMap: почему порядок произволен и что такое entry

HashMap в Rust — реализация SwissTable из библиотеки hashbrown, встроенной в std с версии 1.36. Из её устройства растут два практических следствия.

Первое: порядок обхода не определён и меняется между запусками. Хешер по умолчанию — SipHash-1-3 со случайным ключом, генерируемым при старте процесса. Это защита от HashDoS: иначе злоумышленник, контролирующий ключи, загнал бы все элементы в одну корзину и превратил O(1) в O(n). Вывод для тестов: никогда не сравнивайте format!("{:?}", map) с эталонной строкой — тест будет мигать. Нужен детерминизм — BTreeMap или сортировка перед сравнением.

Второе: вставка инвалидирует ссылки внутрь карты, поэтому borrow checker не даёт держать &mut на значение и одновременно вставлять. Вот код, который выглядит естественно и не компилируется:

use std::collections::HashMap;
let mut m: HashMap<String, u32> = HashMap::new();
for w in words {
    match m.get_mut(*w) {
        Some(c) => *c += 1,
        None => { m.insert(w.to_string(), 1); }
    }
}

error[E0499]: cannot borrow `m` as mutable more than once at a time
  --> src/main.rs:8:23
   |
6  |         match m.get_mut(*w) {
   |               ------------- first mutable borrow occurs here
7  |             Some(c) => *c += 1,
8  |             None => { m.insert(w.to_string(), 1); }
   |                       ^ second mutable borrow occurs here
9  |         }
   |         - first borrow might be used here, when `m` is dropped

Это знаменитый «problem case #3» из RFC 2094: человек видит, что в ветке None заимствование уже не нужно, а компилятор — нет. Проверка на базе Polonius это когда-нибудь освоит; сегодня ответ такой:

for w in words {
    *m.entry(w.to_string()).or_insert(0) += 1;   // одно хеширование, один поиск
}

entry — не обход ограничения, а лучшая версия кода: одно хеширование вместо двух-трёх. Полезные формы: or_insert_with(Vec::new) (не создаёт вектор, если ключ есть), or_default(), and_modify(|v| *v += 1).or_insert(1). Единственная цена — entry требует владения ключом, даже если ключ уже в карте; для дорогих ключей это повод сначала попробовать get_mut.

Смена хешера — самая дешёвая оптимизация в Rust, если ключи не приходят извне: rustc_hash::FxHashMap быстрее в 2–4 раза на числовых ключах, ahash — быстрый и с защитой от коллизий, indexmap::IndexMap сохраняет порядок вставки (часто именно этого и хотят от HashMap). Для недоверенного ввода оставляйте SipHash.

Остальные три: диапазоны, очередь, приоритеты

use std::collections::{BTreeMap, BinaryHeap, VecDeque};
use std::cmp::Reverse;

// BTreeMap — единственная карта в std, умеющая диапазонные запросы
let events = BTreeMap::from([(100, "старт"), (250, "ошибка"), (400, "стоп")]);
for (ts, what) in events.range(150..=300) { println!("{ts}: {what}"); }   // 250: ошибка
println!("{:?}", events.first_key_value());                              // Some((100, "старт"))

// BinaryHeap — это МАКСИ-куча; мини-куча делается обёрткой Reverse
let mut heap = BinaryHeap::from(vec![Reverse(5), Reverse(1), Reverse(9)]);
let Reverse(smallest) = heap.pop().unwrap();
assert_eq!(smallest, 1);

// VecDeque — кольцевой буфер, поэтому данные могут лежать двумя кусками
let mut q = VecDeque::from(vec![1u8, 2, 3]);
q.push_front(0);
let (a, b) = q.as_slices();          // ДВА среза, а не один
let one: &[u8] = q.make_contiguous();  // если нужен один — попросите явно, это O(n)

BTreeMap в std — не бинарное дерево, а B-дерево с несколькими элементами в узле, что даёт хорошую локальность: для маленьких карт (до сотни элементов) он часто быстрее HashMap, потому что не считает хеш. Грабля с as_slices() стоит упоминания: код, передающий VecDeque в функцию с параметром &[T], приходится переписывать.

Адаптеры: карта территории

Адаптер — метод Iterator, возвращающий другой итератор. Их около сорока; вот те, что реально нужны.

filter_map вместо filter + map, если предикат и преобразование — это на самом деле одна операция «разобрать, если получится»:

let raw = ["12", "нет", "7", "", "40"];

let a: Vec<i32> = raw.iter().filter(|s| s.parse::<i32>().is_ok())   // parse дважды на элемент
                            .map(|s| s.parse().unwrap())
                            .collect();

let b: Vec<i32> = raw.iter().filter_map(|s| s.parse().ok()).collect();   // идиоматично
assert_eq!(b, vec![12, 7, 40]);

Clippy ловит первый вариант линтом manual_filter_map. Вообще, cargo clippy знает про итераторы больше среднего разработчика: needless_collect, map_clone, iter_nth, unnecessary_fold, redundant_closure — все про этот раздел (полный список).

peekable: peek требует &mut self, потому что заглянуть вперёд можно только вытащив элемент и спрятав его в буфер. Это удивляет всех. Удобнее next_if:

let mut digits = "42abc".chars().peekable();
let mut num = String::new();
while let Some(c) = digits.next_if(|c| c.is_ascii_digit()) { num.push(c); }
assert_eq!(num, "42");

windows и chunks — методы срезов, а не итераторов. На Iterator их нет принципиально: скользящее окно должно отдавать ссылку на свой внутренний буфер, а next() этого не умеет (причина — ниже, в разделе про пределы модели).

let data = [1, 3, 6, 10, 15];
let diffs: Vec<i32> = data.windows(2).map(|w| w[1] - w[0]).collect();
assert_eq!(diffs, vec![2, 3, 4, 5]);

// chunks_exact быстрее chunks: длина куска известна компилятору
let bytes: &[u8] = &[1, 0, 0, 0, 2, 0, 0, 0, 9, 9];
for c in bytes.chunks_exact(4) { println!("{}", u32::from_le_bytes(c.try_into().unwrap())); }
println!("хвост: {:?}", bytes.chunks_exact(4).remainder());      // [9, 9]

Скользящее окно над настоящим итератором даёт крейт itertools (tuple_windows), он же добавляет unique, sorted, chunk_by, join. Это первый крейт, который стоит добавлять после serde и anyhow.

Потребители: всё это fold

Потребитель доводит итератор до конца (или до нужного места) и возвращает не-итератор. Фундамент один — свёртка; остальное её специализации (sum, product, count, min_by_key, for_each, collect, partition, unzip).

let v = [1, 2, 3, 4];
let sum = v.iter().fold(0, |acc, x| acc + x);      // 10
let max = v.iter().copied().reduce(i32::max);      // Some(4) — fold без начального значения

Отдельная группа — замыкающиеся досрочно: find, find_map, position, any, all, nth, try_fold, try_for_each. Они возвращают управление, как только ответ известен; на бесконечном итераторе работают только они.

let has_big = (1..).map(|x| x * x).any(|x| x > 1_000);   // завершается, хотя источник бесконечен
assert!(has_big);

fn sum_checked(xs: &[u8]) -> Option<u8> {
    xs.iter().try_fold(0u8, |acc, &x| acc.checked_add(x))   // обрыв на первом None
}
assert_eq!(sum_checked(&[100, 100]), Some(200));
assert_eq!(sum_checked(&[200, 100]), None);                 // переполнение u8

Про sum — неочевидное: он не защищён от переполнения. В отладочной сборке iter().sum::<u8>() при переполнении паникует, в релизной тихо оборачивается по модулю. Это общее поведение арифметики в Rust (подробности — в основах); для денег и счётчиков суммируйте в широкий тип: .map(|&x| x as u64).sum::<u64>().

Про сложность: count() в общем случае O(n) — честно крутит итератор. Но для slice::Iter реализация переопределена и просто возвращает длину, O(1). По цепочке такие переопределения не наследуются: v.iter().filter(p).count() — снова O(n).

collect — самая перегруженная функция стандартной библиотеки

collect не «превращает в вектор». Он строит любой тип, реализующий FromIterator, и целевой тип выбирает вызывающая сторона:

use std::collections::{BTreeSet, HashMap, HashSet};
let words = ["b", "a", "b", "c"];

let v: Vec<&str>            = words.iter().copied().collect();
let s: String               = words.iter().copied().collect();          // "babc"
let set: HashSet<&str>      = words.iter().copied().collect();          // 3 элемента
let sorted: BTreeSet<&str>  = words.iter().copied().collect();          // a, b, c
let m: HashMap<&str, usize> = words.iter().copied().zip(1..).collect(); // пары -> карта

Раз тип выбирает вызывающая сторона, забыть его — самая частая ошибка новичка:

error[E0282]: type annotations needed
 --> src/main.rs:2:9
  |
2 |     let squares = (1..=5).map(|x| x * x).collect();
  |         ^^^^^^^
  |
help: consider giving `squares` an explicit type
  |
2 |     let squares: Vec<_> = (1..=5).map(|x| x * x).collect();
  |                +++++++++

Второй вариант той же ошибки — тип указан, но не тот. let copy: Vec<i32> = v.iter().collect(); даёт:

error[E0277]: a value of type `Vec<i32>` cannot be built from an iterator
              over elements of type `&i32`
 --> src/main.rs:3:35
  |
3 |     let copy: Vec<i32> = v.iter().collect();
  |                                   ^^^^^^^ value of type `Vec<i32>` cannot be
  |                                           built from `Iterator<Item=&i32>`
  |
  = help: the trait `FromIterator<&i32>` is not implemented for `Vec<i32>`

Читается прямо: «Vec<i32> нельзя построить из элементов &i32». Лечится .copied(), .cloned() или сменой цели на Vec<&i32>. Turbofish collect::<Vec<_>>() — альтернатива аннотации переменной, полезная в середине цепочки.

Самый красивый трюк — FromIterator для Result и Option. Итератор по Result<T, E> собирается в Result<Vec<T>, E>, обрываясь на первой ошибке:

fn parse_all(input: &str) -> Result<Vec<i32>, std::num::ParseIntError> {
    input.split(',').map(|s| s.trim().parse()).collect()   // Vec<Result<..>> -> Result<Vec<..>>
}
assert_eq!(parse_all("1, 2, 3").unwrap(), vec![1, 2, 3]);
assert!(parse_all("1, ой, 3").is_err());                  // "3" даже не разбирался

Работает так же для Option<Vec<T>> и Result<HashMap<K, V>, E>. Если же нужны и удачи, и ошибки одновременно — не изобретайте цепочку с partition и unwrap, напишите цикл с match. Честный цикл в Rust не считается вторым сортом.

Эффективность: где «zero-cost» выполняется, а где нет

Что действительно бесплатно. Мономорфизация превращает Map<Filter<Iter>> в конкретный тип, все next() встраиваются, LLVM видит один плоский цикл: ни аллокаций, ни виртуальных вызовов, ни обёрток вокруг элементов. Более того, итератор часто быстрее индексного цикла, потому что в нём по построению нет проверок границ:

let mut sum = 0i64;
for i in 0..v.len() { sum += v[i] as i64; }        // проверка i < len на каждой итерации

let sum: i64 = v.iter().map(|&x| x as i64).sum();  // проверок нет: выйти за границы нельзя

Честности ради: в таком простом виде LLVM обычно убирает проверку и в первом варианте. Разница становится измеримой, когда индексов два (a[i] + b[i]) или когда индекс приходит откуда-то ещё — тогда доказать безопасность оптимизатор не может. Идиоматичный ответ на «два массива» — zip, он снимает обе проверки: a.iter().zip(&b).map(|(x, y)| x + y).

Где ленивость помогает алгоритмически. it.take(10).collect() на источнике из миллиона элементов делает десять шагов. Это смена асимптотики — O(k) вместо O(n), — а не микрооптимизация.

Где есть настоящая цена. Первое — size_hint. collect в Vec использует нижнюю границу подсказки, чтобы сразу выделить память:

let a = (0..1000).map(|x| x * 2);
assert_eq!(a.size_hint(), (1000, Some(1000)));   // collect: одна аллокация
let b = (0..1000).filter(|x| x % 3 == 0);
assert_eq!(b.size_hint(), (0, Some(1000)));      // collect: вектор будет расти с нуля

Для длинных filter-цепочек в горячем коде это заметно; лечится вручную (with_capacity + extend). Итераторы с точно известной длиной помечены TrustedLen — тогда collect аллоцирует ровно один раз.

Второе — внутренняя итерация. fold, try_fold и for_each переопределены у Chain, Flatten, FlatMap: вместо «отдать один элемент и вернуть управление» они крутят цикл у себя. На flat_map разница бывает двукратной, так что for_each — не просто стилистическая альтернатива for, а matrix.iter().flatten().copied().sum() может обогнать вложенный цикл.

Третье — время компиляции и объём кода. Каждый адаптер порождает новый тип, каждая комбинация мономорфизируется отдельно. Цепочка из пятнадцати адаптеров в дженерик-функции, вызванной с пятью типами, — это большой объём IR для LLVM. Способы урезать: вынести цепочку в функцию с impl Iterator, а в тяжёлых случаях стереть тип через Box<dyn Iterator>, заплатив виртуальными вызовами за скорость сборки.

fn evens(v: &[i32]) -> impl Iterator<Item = i32> + '_ {
    v.iter().copied().filter(|x| x % 2 == 0)
}
// в редакции 2024 время жизни захватывается автоматически, `+ '_` можно опустить

И четвёртое, о чём молчат: бенчмаркать надо, а не верить. (1..=1000).sum::<u64>() компилятор свернёт в константу; ваша похожая цепочка — нет. Методика — в «Измерении» и «Бенчмаркинге», инструменты для Rust (criterion, divan) — в статье про тестирование.

Галерея грабель

1. collect в середине цепочки — самая частая потеря производительности в Rust-коде вообще:

let n = data.iter().map(f).collect::<Vec<_>>().iter().filter(|x| p(x)).count();  // лишний вектор
let n = data.iter().map(f).filter(|x| p(x)).count();                            // хорошо

Clippy сигналит линтом needless_collect. collect оправдан, когда нужен второй проход, сортировка или освобождение заимствования источника.

2. .chars().nth(i) как индексация строки. Это O(i), потому что UTF-8 — переменной длины; именно поэтому строку в Rust нельзя индексировать. Нужен посимвольный доступ — либо Vec<char> (вчетверо больше памяти, зато O(1)), либо char_indices(). И помните: s.len() — байты, s.chars().count() — скаляры Unicode, а «символ» в человеческом смысле — графемный кластер, для него нужен крейт unicode-segmentation.

3. Сортировка строк «по алфавиту».

let mut names = vec!["Ваня", "аня", "Боря"];
names.sort_unstable();
println!("{names:?}");   // ["Боря", "Ваня", "аня"] — порядок байт UTF-8, не алфавит

Заглавные кириллические буквы идут раньше строчных: сравнение байтовое. Для человеческого порядка нужна коллация (icu_collator) или хотя бы ключ s.to_lowercase().

4. sort_by_key, который не компилируется — классическая стена. users.sort_by_key(|u| &u.name) даёт:

error: lifetime may not live long enough
  |
  |     users.sort_by_key(|u| &u.name);
  |                        -- ^^^^^^^ returning this value requires that
  |                        |          `'1` must outlive `'2`
  |                        has type `&'1 User`

sort_by_key не умеет возвращать ключ, заимствованный из элемента. Ответ — sort_by(|a, b| a.name.cmp(&b.name)); для Copy-ключей (|u| u.age) sort_by_key работает прекрасно.

5. Выбор сортировки. sort — стабильная, аллоцирует буфер; sort_unstable — нестабильная, без аллокаций, обычно быстрее; sort_by_cached_key — когда извлечение ключа дорогое. По умолчанию берите sort_unstable. С Rust 1.81 под капотом современные driftsort и ipnsort — про сами алгоритмы см. «Сортировки».

6. dedup без сортировки. Vec::dedup удаляет только подряд идущие дубликаты, поэтому без sort_unstable() перед ним он почти бесполезен.

7. cloned() там, где хватит copied(). Для Copy-типов copied() выражает намерение точнее и не даёт случайно клонировать String. А map(|x| x.clone()) вместо cloned() — линт map_clone.

8. Итератор, использованный дважды. Потребитель забирает self по значению, «переиспользовать» итератор нельзя — будет use of moved value. Нужно потребить часть и продолжить — by_ref:

let mut it = 1..10;
let head: Vec<i32> = it.by_ref().take(3).collect();   // [1, 2, 3]
let tail: Vec<i32> = it.collect();                    // [4, 5, 6, 7, 8, 9]

9. Двойное разыменование в замыканиях. v.iter().filter(|x| **x > 2) — filter даёт &Item, а Item уже &i32. Лечится образцом в параметре: filter(|&&x| x > 2).

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

Реализовать Iterator — это написать next(). Всё остальное, включая сорок адаптеров, вы получаете бесплатно:

/// Числа Фибоначчи, аккуратно заканчивающиеся на переполнении u64
struct Fib { a: u64, b: u64 }

impl Iterator for Fib {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        let next = self.a.checked_add(self.b)?;   // None -> итератор исчерпан
        self.a = self.b;
        self.b = next;
        Some(self.a)
    }
}

fn main() {
    let first: Vec<u64> = Fib { a: 0, b: 1 }.take(10).collect();
    println!("{first:?}");                        // [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    println!("{}", Fib { a: 0, b: 1 }.count());    // 92 — столько влезает в u64
}

Если состояние простое, свой тип не нужен — в std::iter есть готовые конструкторы successors, from_fn, once, empty, repeat_with:

let powers: Vec<u64> = std::iter::successors(Some(1u64), |&x| x.checked_mul(2))
    .take_while(|&x| x < 1000)
    .collect();                                   // [1, 2, 4, ..., 512]

Дополнительные трейты, которые стоит реализовывать: DoubleEndedIterator (даёт rev, rfind), ExactSizeIterator (даёт len), FusedIterator (обещание «после None только None»), Extend и FromIterator (позволяют extend и collect в вашу коллекцию). И реализуйте size_hint, если знаете длину: это прямо влияет на аллокации у пользователей вашего кода.

Пределы модели

Нельзя отдавать ссылку на внутренний буфер. Сигнатура fn next(&mut self) -> Option<Self::Item> не связывает Item с временем жизни заимствования self, поэтому итератор не может вернуть ссылку на то, что сам перезапишет на следующем шаге. Отсюда отсутствие Iterator-версии windows и то, что BufRead::lines() аллоцирует новый String на каждую строку. «Одалживающий итератор» выражается через GAT, но не совместим ни с одним стандартным адаптером:

trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

Практический ответ в горячем коде — цикл с переиспользуемым буфером:

let mut line = String::new();
while reader.read_line(&mut line)? != 0 {
    process(&line);
    line.clear();          // одна аллокация на весь файл вместо одной на строку
}

Нет асинхронной итерации в std. next() не может быть await: это не async fn. Асинхронные последовательности живут в трейте Stream из futures/tokio-stream со своей вселенной адаптеров; в редакции 2024 gen зарезервировано как ключевое слово под будущие генераторы. Подробно — в статье про async.

Длинные цепочки читаются хуже цикла. Пять адаптеров с замыканиями по три строки — это не идиоматичный Rust, это ребус. Если цепочка не читается вслух одним предложением, разбейте её на именованные функции. И отдельная боль: когда компилятор не может вывести тип замыкания в середине цепочки, диагностика указывает на collect в конце, а причина — в третьем адаптере. Приём отладки — временно разбить цепочку на let с явными типами.

Параллелизм одной строкой: rayon

Раз итератор — это описание работы, а не выполнение, его можно выполнить иначе. rayon даёт параллельные итераторы с почти тем же API:

use rayon::prelude::*;

let total: u64 = files.iter().map(|f| checksum(f)).sum();       // было
let total: u64 = files.par_iter().map(|f| checksum(f)).sum();   // стало: работа по всем ядрам

Это работает потому, что система типов уже доказала отсутствие гонок: par_iter требует Send/Sync от элементов и замыканий, и непотокобезопасный код просто не скомпилируется. Когда rayon не нужен: работа на элемент меньше микросекунды, элементов мало, или задача упирается в память, а не в CPU (ориентиры — в «Производительности конкурентного кода»).

Честно о цене

Что вы получаете. Выразительность уровня Python при производительности уровня C. Невозможность инвалидировать итератор или выйти за границы массива. Ленивость, которая меняет асимптотику, а не только константу. Параллелизм заменой одного слова.

Что вы платите. Время компиляции: каждый адаптер — тип, каждая инстанциация — код для LLVM (меры те же, что везде в Rust: воркспейс, cargo check, линкер mold, sccache — см. инструментарий). Кривую обучения: двойные разыменования, iter против into_iter, collect без аннотации, стена sort_by_key. Пределы выразимости: одалживающие итераторы, асинхронная итерация, скользящие окна над произвольным источником требуют либо крейта, либо цикла. И соблазн переусложнить: возможность выразить всё цепочкой не означает, что нужно.

Где это избыточно. Если программа обрабатывает сто элементов раз в минуту, разница между filter_map и filter().map() не существует — берите то, что читается. Все оптимизации из раздела про эффективность имеют смысл, когда данных много или код в горячем цикле, то есть ровно там, где Rust и выбирают.

Мини-итог

• Итератор — машина состояний с методом next(), а не коллекция и не поток. Адаптеры не выполняют работу, а строят вложенный тип, который компилятор растворяет в цикле.
• Ленивость — следствие устройства. #[must_use] и текст iterators are lazy and do nothing unless consumed — ваш друг.
• iter() / iter_mut() / into_iter() дают &T / &mut T / T. for x in v съедает v; ошибка E0382 объясняет это лучше любой документации.
• Коллекция по умолчанию — Vec. Ключ без порядка — HashMap, с порядком и диапазонами — BTreeMap, очередь с двух концов — VecDeque, приоритеты — BinaryHeap. LinkedList — практически никогда.
• Реаллокация Vec перемещает данные, поэтому мутация во время обхода — ошибка E0502, а не UB. Инструменты вместо борьбы: retain, iter_mut, drain, индексы.
• Порядок обхода HashMap произволен из-за случайного ключа SipHash: не завязывайте на него тесты. entry — не костыль, а способ хешировать один раз.
• collect строит любой FromIterator-тип, включая Result<Vec<T>, E> с обрывом на первой ошибке. Забытая аннотация — E0282, неверный тип элемента — E0277.
• «Zero-cost» реален, но не абсолютен: следите за size_hint и преаллокацией, за лишними collect в середине, за внутренней итерацией у Flatten и за временем компиляции.
• Rust-специфичные грабли: chars().nth, байтовая сортировка строк, sort_by_key с заимствованным ключом, dedup без sort, **x в замыканиях, remove(0) в цикле.
• Модель ломается на одалживающих итераторах и асинхронности. Там цикл — правильный ответ, а не признание поражения.

Источники

• The Rust Programming Language, глава 8 «Common Collections» и глава 13 «Iterators and Closures» — канонический вход.
• Документация модуля std::collections — раздел «Which collection should you use?» с таблицей асимптотик.
• Трейт Iterator и модуль std::iter — все адаптеры с примерами, лучший справочник по теме.
• Nicholas Nethercote, «The Rust Performance Book»: главы «Iterators» и «Collections» — измеренные, а не выдуманные советы.
• Jim Blandy, Jason Orendorff, Leonora Tindall, «Programming Rust», 2nd ed. — главы 15 и 16 остаются лучшим печатным разбором итераторов и коллекций.
• Jon Gjengset, «Rust for Rustaceans» — про size_hint, специализацию и цену мономорфизации.
• hashbrown и доклад Matt Kulukundis «Designing a Fast, Efficient, Cache-friendly Hash Table» — устройство SwissTable из первых рук.
• «Learn Rust With Entirely Too Many Linked Lists» — почему связные списки в Rust больно.
• itertools и rayon — два крейта, доводящие итераторы до практической полноты.
• Clippy lint list — фильтр по группе perf даёт готовый чек-лист по коллекциям и итераторам.
• RFC 2094 «Non-Lexical Lifetimes» — раздел «problem cases» объясняет, почему существует entry.
• Rust Error Codes Index — расшифровка E0277, E0282, E0382, E0499, E0502; локально то же даёт rustc --explain E0502.

Что дальше

Бесстрашная конкурентность: потоки, каналы, Send и Sync, разделяемое состояние — мы только что видели, как par_iter() превращает последовательный код в параллельный без единой гонки. Дальше разберём, откуда берётся эта гарантия: как правило «один писатель или много читателей» распространяется на потоки, что означают автотрейты Send и Sync, почему Rc нельзя послать в другой поток, а Arc можно, и как выглядит разделяемое состояние, которое компилятор согласен пропустить.