Использование и применение std::collections в Rust: BTreeMap, HashSet, BinaryHeap и VecDeque

Введение

#

В языке Rust обычно используеются стандартные Vec<T> и HashMap<K, V>. Но когда дело доходит до очередей сообщений, каких-то выборок или планировщиков задач - дефолтных контейнеров уже становится маловато.

Стандартный модуль std::collections закрывает большинство прикладных задач без внешних крейтов. Но при этом важно замечать не только на оценку скорости выполнения O(1) или O(log N), но и на то, как данные размещаются в памяти. Современные процессоры любят работать с непрерывными кусками памяти: удачное размещение данных и попадание в L1/L2 кэш процессора на практике это часто перекрывают теоретическую сложность алгоритмов.

Разберем четыре ключевые структуры из стандартной библиотеки: VecDeque, BTreeMap, BTreeSet и BinaryHeap.

1. Коллекции: VecDeque vs Vec vs LinkedList

#

Динамический массив (Vec<T>)

#

Vec<T> хранит элементы в виде непрерывного массива в куче. За счет этого итерация по вектору работает очень быстро, а чтение по индексу оценивается как O(1).

Слабое место вектора — вставка и удаление в начале или середине: для этого приходится сдвигать весь хвост массива за O(N).

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

#

Если вам нужна очередь (FIFO) или кольцевой буфер последних событий, берите VecDeque<T>.

Под капотом - динамический кольцевой буфер:

• Вставка и удаление с конца (push_back / pop_back) — O(1).
• Вставка и удаление с начала (push_front / pop_front) — O(1) без сдвига всего массива.

Связный список (LinkedList<T>)

#

Двунаправленный LinkedList<T> в реальном коде на Rust почти не встречается. Каждый узел живет в куче в собственной аллокации. При обходе списка процессор вынужден постоянно прыгать по памяти и ловить промахи по кешу.

2. Словари: BTreeMap vs HashMap

#

стандартная библиотека предлагает два инструмента для работы с парами ключ-значение.

Хеш-таблицы (HashMap<K, V> и HashSet<T>)

#

• Под капотом: алгоритм SwissTable.
• Сложность: поиск, вставка и удаление в среднем занимают O(1).
• Особенности: порядок элементов случаен. Для ключей обязательны типажи Hash + Eq.

B-деревья (BTreeMap<K, V> и BTreeSet<T>)

#

• Под капотом: B-дерево, где в каждом узле хранится компактный массив элементов. Это отлично укладывается в кэш-линии процессора.
• Сложность: поиск, вставка и удаление гарантированно занимают O(log N).
• Особенности: ключи всегда отсортированы. Для ключей требуется типаж Ord.

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "Третий");
map.insert(1, "Первый");

// Итерация гарантированно вернет элементы по возрастанию: 1, затем 3
for (key, val) in &map {
    println!("{key}: {val}");
}

3. Очередь с приоритетом: BinaryHeap

#

BinaryHeap<T> — это двоичная Max-куча реализованная поверх вектора. Коллекция создана для планировщиков задач и очередей событий, где первым нужно обрабатывать самый приоритетный элемент.

• Добавление элемента .push(item) занимает O(log N).
• Извлечение максимального элемента .pop() занимает O(log N).
• Подсмотреть максимальный элемент через .peek() можно за O(1).

4. Шпаргалка по сложности

#

Ниже — интерактивные слайды для каждой коллекции:

 1use std::collections::VecDeque;
 2
 3fn main() {
 4    // Двусторонняя очередь (Ring Buffer)
 5    let mut queue = VecDeque::with_capacity(5);
 6
 7    // Добавление в конец очереди:
 8    queue.push_back("Задача 1");
 9    queue.push_back("Задача 2");
10
11    // Срочное добавление в начало очереди:
12    queue.push_front("Приоритетная задача!");
13
14    println!("Элементы очереди: {:?}", queue);
15
16    // Извлечение с противоположных концов за O(1):
17    if let Some(first) = queue.pop_front() {
18        println!("Обработана из начала: {first}");
19    }
20
21    if let Some(last) = queue.pop_back() {
22        println!("Обработана с конца: {last}");
23    }
24}
25

 1use std::collections::BTreeMap;
 2
 3fn main() {
 4    let mut sensor_data = BTreeMap::new();
 5
 6    // Вставка ключей в случайном порядке
 7    sensor_data.insert(104, "Серверная");
 8    sensor_data.insert(101, "Прихожая");
 9    sensor_data.insert(103, "Кухня");
10    sensor_data.insert(102, "Гостиная");
11
12    println!("--- Итерация всегда строго отсортирована по ключу ---");
13    for (id, room) in &sensor_data {
14        println!("Датчик ID {id}: {room}");
15    }
16
17    println!("\n--- Срез по диапазону ключей (Range query 102..=103) ---");
18    for (id, room) in sensor_data.range(102..=103) {
19        println!("Диапазон: ID {id} -> {room}");
20    }
21}
22

 1use std::cmp::Ordering;
 2use std::collections::BinaryHeap;
 3
 4#[derive(Eq, PartialEq)]
 5struct Job {
 6    priority: u32,
 7    name: String,
 8}
 9
10// Реализуем Ord для сортировки очереди по приоритету
11impl Ord for Job {
12    fn cmp(&self, other: &Self) -> Ordering {
13        self.priority.cmp(&other.priority)
14    }
15}
16
17impl PartialOrd for Job {
18    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
19        Some(self.cmp(other))
20    }
21}
22
23fn main() {
24    let mut heap = BinaryHeap::new();
25
26    heap.push(Job { priority: 10, name: "Фоновая отгрузка логов".to_string() });
27    heap.push(Job { priority: 90, name: "Аварийное отключение питания".to_string() });
28    heap.push(Job { priority: 50, name: "Обновление конфигурации".to_string() });
29
30    println!("--- Выборка задач в порядке приоритета (Max-Heap) ---");
31    while let Some(job) = heap.pop() {
32        println!("Выполняется [Приоритет {}]: {}", job.priority, job.name);
33    }
34}
35

Тест для самопроверки

#

Несколько вопросов, чтобы закрепить различия между коллекциями: