Глава 18: Обзор стандартной библиотеки

Раздел 4: Коллекции

В этом разделе мы познакомимся с модулем std::collections — частью стандартной библиотеки Rust, которая предоставляет набор мощных структур данных для хранения и управления набором элементов. Мы подробно разберём динамические массивы (Vec), хэш-таблицы (HashMap и HashSet) и сбалансированные деревья (BTreeMap и BTreeSet). Лекция подойдёт как новичкам, только начинающим изучать Rust, так и опытным разработчикам, желающим углубить свои знания. Мы рассмотрим особенности, примеры использования и тонкости выбора подходящей коллекции.

1. std::collections: Обзор структур данных

Модуль std::collections содержит коллекции — контейнеры для хранения множества элементов. В отличие от базовых типов, таких как массивы фиксированной длины ([T; N]), коллекции в std::collections динамичны и предлагают гибкость для различных задач. Они оптимизированы для производительности и безопасности, что делает их неотъемлемой частью разработки на Rust.

Основные характеристики коллекций в Rust:

• Динамичность: Размер может изменяться во время выполнения.
• Типобезопасность: Все элементы имеют один тип, определённый при создании.
• Владение: Коллекции владеют своими данными и управляют памятью.
• Итераторы: Поддерживают удобную работу через методы вроде iter(), map() и filter().

Давайте разберём ключевые структуры данных из std::collections, указанные в плане: Vec, HashMap, HashSet, BTreeMap и BTreeSet.

1.1 Динамические массивы: Vec

Vec — это динамический массив, который растёт или уменьшается по мере добавления или удаления элементов. Это одна из самых часто используемых коллекций в Rust благодаря своей простоте и скорости доступа по индексу.

Особенности:

• Хранит элементы в непрерывной области памяти.
• Доступ по индексу — O(1).
• Добавление в конец — O(1) в среднем, но может быть O(n) при перевыделении памяти.

Пример: работа с Vec:

use std::collections::Vec;

fn main() {
    // Создаём пустой Vec
    let mut numbers: Vec = Vec::new();
    
    // Добавляем элементы
    numbers.push(1);
    numbers.push(2);
    numbers.push(3);
    
    // Доступ по индексу
    println!("Первый элемент: {}", numbers[0]);
    
    // Итерация
    for num in &numbers {
        println!("Число: {}", num);
    }
    
    // Удаляем последний элемент
    if let Some(last) = numbers.pop() {
        println!("Удалён: {}", last);
    }
}
    

Комментарии:

• push добавляет элемент в конец.
• pop возвращает Option, так как Vec может быть пустым.
• Доступ по индексу паникует при выходе за границы, если не использовать get().

1.2 Хэш-таблицы: HashMap

HashMap — это ассоциативный массив, который хранит пары "ключ-значение". Он использует хэширование для быстрого доступа к данным по ключу.

Особенности:

• Доступ по ключу — O(1) в среднем.
• Ключи должны реализовать трейты Eq и Hash.
• Не сохраняет порядок элементов.

Пример: подсчёт слов в тексте:

use std::collections::HashMap;

fn main() {
    let text = "hello world hello rust world";
    let mut word_count = HashMap::new();
    
    // Подсчитываем слова
    for word in text.split_whitespace() {
        *word_count.entry(word).or_insert(0) += 1;
    }
    
    // Выводим результат
    for (word, count) in &word_count {
        println!("Слово '{}': {} раз", word, count);
    }
}
    

Комментарии:

• entry возвращает Entry, позволяя модифицировать значение или вставить новое.
• or_insert добавляет значение по умолчанию (здесь 0), если ключа нет.

1.3 Хэш-таблицы: HashSet

HashSet — это множество, которое хранит уникальные элементы без дубликатов. Оно похоже на HashMap, но без значений, только ключи.

Особенности:

• Проверка наличия элемента — O(1) в среднем.
• Элементы должны реализовать Eq и Hash.
• Полезно для операций с множествами (объединение, пересечение).

Пример: удаление дубликатов:

use std::collections::HashSet;

fn main() {
    let numbers = vec![1, 2, 2, 3, 3, 4];
    let unique: HashSet = numbers.into_iter().collect();
    
    println!("Уникальные числа: {:?}", unique);
}
    

Комментарии:

• collect преобразует итератор в HashSet.
• Дубликаты автоматически удаляются.

1.4 Деревья: BTreeMap

BTreeMap — это отсортированная карта, реализованная на основе B-дерева. В отличие от HashMap, она сохраняет порядок ключей.

Особенности:

• Доступ по ключу — O(log n).
• Ключи должны реализовать Ord.
• Итерация происходит в порядке ключей.

Пример: отсортированная таблица:

use std::collections::BTreeMap;

fn main() {
    let mut scores = BTreeMap::new();
    scores.insert("Alice", 95);
    scores.insert("Bob", 87);
    scores.insert("Charlie", 92);
    
    for (name, score) in &scores {
        println!("{}: {}", name, score);
    }
}
    

Комментарии:

• Вывод будет в порядке: Alice, Bob, Charlie.
• Подходит для задач, где нужен порядок или диапазонные запросы.

1.5 Деревья: BTreeSet

BTreeSet — это отсортированное множество, аналогичное HashSet, но с упорядоченными элементами.

Особенности:

• Проверка наличия — O(log n).
• Элементы должны реализовать Ord.
• Поддерживает операции с диапазонами.

Пример: диапазон чисел:

use std::collections::BTreeSet;

fn main() {
    let mut numbers = BTreeSet::new();
    numbers.insert(5);
    numbers.insert(2);
    numbers.insert(8);
    
    // Элементы от 2 до 6
    let range: Vec<_> = numbers.range(2..=6).collect();
    println!("Диапазон: {:?}", range); // [2, 5]
}
    

Комментарии:

• range возвращает итератор по элементам в заданном диапазоне.
• Подходит для задач с упорядоченными данными.

Практические советы

• Выбор коллекции: Используйте Vec для последовательного доступа, HashMap/HashSet для быстрого поиска, BTreeMap/BTreeSet для упорядоченности.
• Производительность: Указывайте начальную ёмкость (with_capacity) для Vec, HashMap и HashSet, если размер известен.
• Итераторы: Предпочитайте методы вроде iter() и into_iter() вместо индексов для большей выразительности.
• Типы ключей: Убедитесь, что ваши ключи реализуют нужные трейты (Hash, Eq, Ord).

Пример: Комбинирование коллекций

Программа для подсчёта уникальных слов и их частоты:

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

fn main() {
    let text = "rust is great rust is fun";
    
    // Уникальные слова в HashSet
    let unique_words: HashSet<&str> = text.split_whitespace().collect();
    println!("Уникальные слова: {:?}", unique_words);
    
    // Частота слов в HashMap
    let mut word_freq = HashMap::new();
    for word in text.split_whitespace() {
        *word_freq.entry(word).or_insert(0) += 1;
    }
    println!("Частота слов: {:?}", word_freq);
}
    

Этот пример демонстрирует, как HashSet и HashMap решают разные задачи с одной и той же данными.

Заключение

Модуль std::collections предоставляет богатый набор структур данных, каждая из которых оптимизирована для своих задач. Vec хорош для последовательного хранения, HashMap и HashSet — для быстрого поиска, а BTreeMap и BTreeSet — для упорядоченных данных. Понимание их особенностей и правильный выбор — ключ к эффективному коду на Rust. В следующих разделах мы рассмотрим другие утилиты стандартной библиотеки, такие как std::fmt.

Выполните упражнение или двигайтесь дальше!