Векторы, HashMap и итераторы в Rust

Vec, HashMap и итераторы

Коллекции спрашивают, чтобы понять, знаешь ли ты цену операций: что происходит при push в заполненный вектор, зачем нужен entry, почему map без collect ничего не делает. Это ежедневный код, и здесь сразу видно, писал ли человек на Rust или пересказывает главу из книги.

Стержень: Vec живёт непрерывно в куче и растёт перевыделением, HashMap даёт доступ через entry и не гарантирует порядок, а итераторы ленивы и ничего не считают без терминальной операции.

// Формулировки: «что будет при push, если ёмкость кончилась?», «зачем entry?», «что напечатает map без collect?»

Рост вектора и его цена

Vec хранит элементы непрерывно, а сам занимает три слова: указатель, длину и ёмкость. Когда место кончается, он выделяет новый буфер (обычно вдвое больше), переносит туда элементы и освобождает старый. Амортизированно push остаётся O(1), но каждое удвоение - реальная работа.

Из этого следуют два практических вывода. Первый: если размер примерно известен, бери Vec::with_capacity - сэкономишь цепочку перевыделений. Второй: ссылка на элемент после роста стала бы висячей, и именно поэтому borrow checker не даёт держать &v[0] и одновременно делать push.

// Проверено: Vec::with_capacity(2) после третьего push показывает ёмкость 4 - то самое удвоение.

capacity: размер выделенного буфера; len - сколько занято
перевыделение: новый буфер с переносом элементов при нехватке места

entry: посмотреть и обновить за один поиск

Классическая задача - посчитать частоты. Наивно это выглядит как get, потом insert: два поиска по ключу и лишний клон. entry возвращает вход в карту: or_insert кладёт значение по умолчанию, только если ключа не было, и в любом случае отдаёт &mut на значение.

Есть и ленивый вариант - or_insert_with, он вызывает замыкание лишь при отсутствии ключа. Разница важна, когда значение по умолчанию дорогое: пустой Vec или запрос куда-нибудь наружу.

// И отдельная деталь про HashMap: порядок обхода не гарантирован и меняется между запусками, потому что сид хеширования рандомизируется. Нужен порядок - бери BTreeMap, он же умеет запросы по диапазону.

let mut m: HashMap<&str, i32> = HashMap::new();
*m.entry("a").or_insert(0) += 1;
*m.entry("a").or_insert(0) += 1; // 2

entry API: доступ к месту в карте с вставкой при отсутствии
BTreeMap: упорядоченная карта: обход по возрастанию и range-запросы

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

v.iter().map(|x| ...) не выполняет замыкание ни разу: map лишь строит адаптер. Работа начинается, когда у итератора запрашивают элементы - collect, sum, for. Без такой терминальной операции не произойдёт ничего, и компилятор ограничится предупреждением must_use.

Рядом живёт вторая частая путаница: iter() отдаёт &T и оставляет коллекцию живой, into_iter() забирает владение и отдаёт сами значения, iter_mut() позволяет менять элементы на месте. Цикл for x in &v это iter(), а for x in v - into_iter(), после которого к v уже не обратиться.

// Полезный приём: collect::<Result<Vec<_>, _>>() собирает коллекцию Result-ов в Result коллекции и обрывается на первой ошибке.

let v = vec![1, 2, 3];
let it = v.iter().map(|x| x * 2); // ничего
let sum: i32 = it.sum();          // 12

ленивый адаптер: map/filter, не выполняющие работу без потребителя
into_iter: итерация с передачей владения элементами

Как отвечать: «Почему map без collect ничего не делает?»

Потому что итераторы в Rust ленивы: map только строит адаптер поверх исходного итератора, а замыкание вызывается тогда, когда у цепочки кто-то запрашивает элементы - collect, sum, for, for_each. Пока терминальной операции нет, работы не происходит, и компилятор напоминает об этом предупреждением must_use. Сделано так ради композиции: можно навесить фильтры и преобразования в цепочку, и всё это пройдёт по данным за один проход, без промежуточных коллекций.

Ты объясняешь не только факт, но и зачем язык так устроен - один проход вместо промежуточных векторов. Это и есть ответ уровня «работал», а не «читал».

На чём валятся

−Пишут map с побочным эффектом без терминальной операции и не понимают, почему тихо.
−Рассчитывают на стабильный порядок обхода HashMap - он рандомизирован.
−Делают get + insert вместо entry: два поиска по ключу вместо одного.
−Держат ссылку на элемент вектора и вызывают push, а потом спорят с компилятором вместо того, чтобы понять про перевыделение.
−Путают iter и into_iter: после второго коллекция уже недоступна.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 13, остальные разбираются в тренажёре.

#rs_collections1 / 5
Что напечатает код?
```
let v = vec![1, 2, 3];
v.iter().map(|x| {
    println!("вижу {}", x);
    x * 2
});
println!("конец");
```
A)«вижу 1/2/3», затем «конец»
B)«конец», затем «вижу 1/2/3» — map откладывается до конца функции
C)Только «конец»: итератор ленив, без потребителя ничего не выполнится
D)Не скомпилируется: результат map обязан быть использован
показать ответ и разбор
+C)Только «конец»: итератор ленив, без потребителя ничего не выполнится
// разбор: map лишь строит адаптер: замыкание вызывается, когда у итератора кто-то запрашивает элементы — sum, collect, for. Без потребителя не выполнится ничего, и компилятор ограничится предупреждением must_use об отброшенном итераторе. Для побочных эффектов берут for_each или обычный for.
#rs_collections2 / 5
Чем for x in &v отличается от for x in v для Vec<String>?
A)Первый копирует элементы, второй работает по ссылке
B)Разницы нет: компилятор сам подставляет заимствование
C)Второй быстрее: он не разыменовывает элементы на каждой итерации
D)Первый даёт ссылки и оставляет вектор живым, второй забирает владение
показать ответ и разбор
+D)Первый даёт ссылки и оставляет вектор живым, второй забирает владение
// разбор: &v вызывает iter() и отдаёт &String — вектор после цикла доступен. Голый v вызывает into_iter(), забирает вектор целиком и отдаёт владеющие String, поэтому обращаться к v после цикла компилятор уже не даст. Третий вариант — &mut v (iter_mut) для правки элементов на месте.
#rs_collections3 / 5
Парсим строки в числа. Что даст collect::<Result<Vec<i32>, _>>() при первой неудачной строке?
A)Вернёт Err, остановив разбор на первой ошибке
B)Вернёт Ok с числами, которые удалось разобрать, ошибки пропустит
C)Соберёт Vec<Result<i32, _>>: тип Result снаружи так не работает
D)Паникует на первой ошибке — collect не умеет возвращать Err
показать ответ и разбор
+A)Вернёт Err, остановив разбор на первой ошибке
// разбор: У Result есть FromIterator: коллекция из Result-ов собирается в Result из коллекции. Итерация прекращается на первом Err, он и возвращается — короткое замыкание без разбора хвоста. Если нужны все успешные значения, берут filter_map(|r| r.ok()), а чтобы увидеть все ошибки — partition.
#rs_collections4 / 5
Когда BTreeMap предпочтительнее HashMap?
A)Когда ключей много: BTreeMap выигрывает на больших объёмах
B)Когда ключи — строки: HashMap работает только с числовыми ключами
C)Когда нужен обход по возрастанию ключа и запросы по диапазону
D)Когда важна потокобезопасность: BTreeMap синхронизирован внутри
показать ответ и разбор
+C)Когда нужен обход по возрастанию ключа и запросы по диапазону
// разбор: BTreeMap хранит ключи упорядоченно: итерация идёт по возрастанию, доступны range-запросы и поиск ближайшего. Плата — O(log n) вместо амортизированного O(1) у HashMap. HashMap же порядок не гарантирует вовсе: он рандомизирует сид хеширования, и порядок обхода меняется между запусками.
#rs_collections5 / 5
Чем Vec<T> отличается от массива [T; N]?
A)Vec растёт в рантайме и держит данные в куче, у массива длина в типе
B)Массив рассчитан на числа, Vec — на строки и структуры
C)Vec индексируется без проверки границ, массив — с проверкой
D)Массив передают в функцию только обёрнутым в Vec
показать ответ и разбор
+A)Vec растёт в рантайме и держит данные в куче, у массива длина в типе
// разбор: Длина массива — часть типа: [i32; 3] и [i32; 4] разные типы, размер известен при компиляции, значение лежит там же, где объявлено. Vec держит буфер в куче и умеет расти, а сам занимает три слова: адрес, длину и ёмкость. Отсюда выбор: размер известен заранее и не меняется — массив, во всех остальных случаях Vec.

дальше

Теорию прочитали. Навык ставится повторением

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

Открыть тренажёр