04. Коллекции и строки

Vec<T> — динамический массив

Vec<T> — основная коллекция общего назначения: непрерывный буфер на куче, растущий при необходимости. Внутри — та же тройка (ptr, len, capacity), что и у String (собственно, String — это по сути обёртка над Vec<u8> с гарантией валидного UTF-8).

fn main() {
    let mut v: Vec<i32> = Vec::new();
    v.push(1);
    v.push(2);

    let v2 = vec![1, 2, 3];               // макрос-конструктор
    let v3 = Vec::with_capacity(100);      // предварительная аллокация — избегаем реаллокаций

    // Безопасный доступ по индексу: get возвращает Option вместо panic
    match v.get(5) {
        Some(val) => println!("{val}"),
        None => println!("нет элемента с индексом 5"),
    }
    // v[5] — вызвал бы panic "index out of bounds"

    for i in &v { println!("{i}"); }        // заимствование элементов
    for i in &mut v { *i += 10; }         // изменяемое заимствование, *i — разыменование
}

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

String vs &str

В Rust два основных строковых типа, и различие между ними — прямое следствие модели владения.

fn main() {
    let literal: &'static str = "hello";   // живёт в бинарнике всю программу
    let owned: String = literal.to_string(); // аллокация на куче + копирование
    let owned2: String = String::from("hello");
    let borrowed: &str = &owned;             // deref-coercion: &String -> &str

    let concatenated = owned2 + " world";      // String + &str -> String (owned2 перемещена в +)
    let formatted = format!("{literal} {borrowed}"); // не забирает владение, гибче +

    println!("{concatenated} {formatted}");
}

UTF-8 и индексация строк

String/&str в Rust — всегда валидный UTF-8. Символ (char) занимает от 1 до 4 байт, поэтому прямая индексация по байтовому смещению (s[0]) запрещена компилятором — она могла бы разрезать многобайтовый символ пополам.

fn main() {
    let hello = String::from("Здравствуй");
    // let c = hello[0]; // ОШИБКА КОМПИЛЯЦИИ: String не реализует Index<usize>

    println!("байт: {}", hello.len());              // 20 — байт, не букв (кириллица — 2 байта на символ)
    println!("символов: {}", hello.chars().count()); // 10

    // Итерация по символам (Unicode scalar values)
    for c in hello.chars() {
        print!("{c}-");
    }

    // Итерация по байтам
    for b in hello.bytes() {
        print!("{b} ");
    }

    // Срез по байтовому диапазону — panic, если граница не на UTF-8 char boundary
    let slice = &hello[0..2]; // "З" — 2 байта, валидная граница
    // let bad = &hello[0..1]; // panic: byte index 1 is not a char boundary
}

HashMap<K, V> и HashSet<T>

HashMap — хеш-таблица общего назначения, использующая по умолчанию криптостойкий (но более медленный) алгоритм SipHash — защита от HashDoS-атак "из коробки". HashSet<T> — по сути HashMap<T, ()>.

use std::collections::{HashMap, HashSet};

fn main() {
    let mut scores: HashMap<String, i32> = HashMap::new();
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    // entry API — вставить-или-обновить без двойного поиска по ключу
    scores.entry(String::from("Blue")).or_insert(0);       // не тронет существующее значение
    *scores.entry(String::from("Red")).or_insert(0) += 1;  // типичный паттерн подсчёта

    match scores.get("Blue") {
        Some(&score) => println!("Blue: {score}"),
        None => println!("нет команды Blue"),
    }

    for (key, value) in &scores { // порядок обхода НЕ гарантирован
        println!("{key}: {value}");
    }

    let mut unique: HashSet<i32> = HashSet::new();
    unique.insert(1);
    unique.insert(1); // дубликат игнорируется
    println!("{}", unique.len()); // 1
}

Владение ключами: вставка String-ключа перемещает его владение в HashMap — карта становится ответственной за его освобождение. Для типа значения ключа нужны трейты Eq и Hash (для кастомных структур — #[derive(Hash, Eq, PartialEq)]).

BTreeMap/BTreeSet — упорядоченные коллекции

В отличие от HashMap, BTreeMap<K, V> хранит записи упорядоченными по ключу (требует Ord) и обходится за O(log n) на операцию вместо амортизированного O(1) у хеш-таблицы — плата за детерминированный порядок и возможность диапазонных запросов.

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<i32, &str> = BTreeMap::new();
    map.insert(3, "three");
    map.insert(1, "one");
    map.insert(2, "two");

    for (k, v) in &map { // обход гарантированно по возрастанию ключа: 1, 2, 3
        println!("{k}: {v}");
    }

    // диапазонные запросы — недоступны у HashMap в принципе
    for (k, v) in map.range(1..3) {
        println!("range: {k}: {v}");
    }
}

VecDeque<T> — двусторонняя очередь

VecDeque реализован как кольцевой буфер (ring buffer) и даёт амортизированное O(1) добавление/удаление с обоих концов — в отличие от Vec, у которого удаление/вставка в начало стоит O(n) (сдвиг всех элементов).

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
    deque.push_back(1);   // O(1) амортизированно
    deque.push_front(0);  // O(1) амортизированно — у Vec было бы O(n)
    deque.push_back(2);

    while let Some(front) = deque.pop_front() {
        println!("{front}"); // 0, 1, 2
    }
}

Итерация с владением: iter(), iter_mut(), into_iter()

У каждой коллекции есть три способа получить итератор, различающиеся тем, что происходит с элементами. Этот выбор напрямую завязан на модель владения из темы 02.

fn main() {
    let v = vec![1, 2, 3];

    for x in v.iter() {      // x: &i32 — заимствование, v остаётся доступной
        print!("{x} ");
    }

    let mut v2 = vec![1, 2, 3];
    for x in v2.iter_mut() {  // x: &mut i32 — изменяемое заимствование
        *x *= 10;
    }

    for x in v.into_iter() {  // x: i32 — забирает владение, v больше недоступна
        print!("{x} ");
    }
    // for x in v { ... } — сахар, эквивалентный into_iter() для владеющих значений
}

Выбор коллекции: сводная таблица