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

> Разбираем коллекции в Rust: когда применять VecDeque, чем BTreeMap отличается от HashMap и почему LinkedList почти никогда не нужен.

- **URL:** https://eagle2000.space/rust/rust-collections-overview/
- **Date:** 2026-09-18

- **Tags:** rust, dev, collections, btreemap, vecdeque, binaryheap

---
## Введение

В языке 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)` без сдвига всего массива.

> [!TIP]
> Почти в любом сценарии, где кажется нужным использовать связный список, `VecDeque` выигрывает и по скорости и по расходу памяти.

### Связный список (`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`.

```rust
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}");
}
```

> [!NOTE]
> Зачем брать `BTreeMap`, если у `HashMap` заявлен `O(1)`?
> 1. Нужна сортировка ключей по умолчанию.
> 2. Нужны выборки по диапазону через `.range(min..max)`.
> 3. Нужны предсказуемые гарантии времени без риска худшего сценария `O(N)` при коллизиях хешей.

---

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

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

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

> [!NOTE]
> Чтобы превратить `BinaryHeap` в Min-кучу (где первым выходит наименьший элемент), оберните значения в `std::cmp::Reverse(x)`.

---

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

| Коллекция | Доступ | Вставка в начало | Вставка в конец | Порядок элементов |
| :--- | :---: | :---: | :---: | :---: |
| **`Vec<T>`** | `O(1)` по индексу | `O(N)` | `O(1)` аморт. | Не сортирован |
| **`VecDeque<T>`** | `O(1)` по индексу | `O(1)` аморт. | `O(1)` аморт. | Не сортирован |
| **`HashMap<K, V>`** | `O(1)` среднее | — | — | Случайный |
| **`BTreeMap<K, V>`** | `O(log N)` | — | — | Отсортирован |
| **`BinaryHeap<T>`** | `O(1)` для Max | — | `O(log N)` | По приоритету |

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


### 💻 Работа с VecDeque, BTreeMap и BinaryHeap


#### Шаг 1

```rust
use std::collections::VecDeque;

fn main() {
    // Двусторонняя очередь (Ring Buffer)
    let mut queue = VecDeque::with_capacity(5);

    // Добавление в конец очереди:
    queue.push_back("Задача 1");
    queue.push_back("Задача 2");

    // Срочное добавление в начало очереди:
    queue.push_front("Приоритетная задача!");

    println!("Элементы очереди: {:?}", queue);

    // Извлечение с противоположных концов за O(1):
    if let Some(first) = queue.pop_front() {
        println!("Обработана из начала: {first}");
    }

    if let Some(last) = queue.pop_back() {
        println!("Обработана с конца: {last}");
    }
}
```

**Двусторонняя очередь: VecDeque**
- `VecDeque<T>` реализован как кольцевой буфер (Ring Buffer).
- Позволяет выполнять вставку и удаление за `O(1)` как с начала (`push_front`/`pop_front`), так и с конца (`push_back`/`pop_back`).
- Идеальный выбор для реализаций FIFO-очередей задач или буферов последних сообщений.


#### Шаг 2

```rust
use std::collections::BTreeMap;

fn main() {
    let mut sensor_data = BTreeMap::new();

    // Вставка ключей в случайном порядке
    sensor_data.insert(104, "Серверная");
    sensor_data.insert(101, "Прихожая");
    sensor_data.insert(103, "Кухня");
    sensor_data.insert(102, "Гостиная");

    println!("--- Итерация всегда строго отсортирована по ключу ---");
    for (id, room) in &sensor_data {
        println!("Датчик ID {id}: {room}");
    }

    println!("\n--- Срез по диапазону ключей (Range query 102..=103) ---");
    for (id, room) in sensor_data.range(102..=103) {
        println!("Диапазон: ID {id} -> {room}");
    }
}
```

**Упорядоченный словарь: BTreeMap**
- `BTreeMap<K, V>` устроен как B-дерево. Ключи всегда хранятся в отсортированном виде.
- Гарантирует логарифмическую сложность `O(log N)` для поиска, вставки и удаления.
- Позволяет выполнять быструю выборку по диапазонам ключей через метод `.range()`.


#### Шаг 3

```rust
use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Job {
    priority: u32,
    name: String,
}

// Реализуем Ord для сортировки очереди по приоритету
impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority)
    }
}

impl PartialOrd for Job {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut heap = BinaryHeap::new();

    heap.push(Job { priority: 10, name: "Фоновая отгрузка логов".to_string() });
    heap.push(Job { priority: 90, name: "Аварийное отключение питания".to_string() });
    heap.push(Job { priority: 50, name: "Обновление конфигурации".to_string() });

    println!("--- Выборка задач в порядке приоритета (Max-Heap) ---");
    while let Some(job) = heap.pop() {
        println!("Выполняется [Приоритет {}]: {}", job.priority, job.name);
    }
}
```

**Очередь с приоритетом: BinaryHeap**
- `BinaryHeap<T>` — это Max-Куча. Метод `.pop()` всегда первым возвращает максимальный элемент.
- Вставка `push()` и удаление `pop()` выполняются за `O(log N)`.
- Требует от типа реализации типажа `Ord` и `Eq`. Идеально подходит для планировщиков задач.


---

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

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


### 📝 Стандартные коллекции в Rust


**1. Какое преимущество дает использование `VecDeque<T>` перед обычным `Vec<T>`?**

- [ ] Возможность быстро вставлять и извлекать элементы с обоих концов за O(1)
- [ ] Автоматическая сортировка элементов при вставке
- [ ] Встроенная многопоточная синхронизация

**2. Чем `BTreeMap<K, V>` отличается от `HashMap<K, V>`?**

- [ ] BTreeMap сохраняет ключи в отсортированном виде и поддерживает выборку по диапазонам .range()
- [ ] BTreeMap всегда работает быстрее HashMap на случайных ключах
- [ ] BTreeMap аллоцируется исключительно на стеке

**3. По какому принципу работает коллекция `BinaryHeap<T>`?**

- [ ] Это Max-куча, которая вызовом .pop() всегда возвращает элемент с максимальным приоритетом
- [ ] Это стандартный двунаправленный связный список
- [ ] Это стек с доступом LIFO

**4. Какова асимптотическая сложность поиска ключа в `BTreeMap`?**

- [ ] O(log N)
- [ ] O(1)
- [ ] O(N^2)

**5. Как превратить `BinaryHeap<T>` в Min-Кучу (очередь, извлекающую сначала наименьшие элементы)?**

- [ ] Обернуть элементы в контейнер `std::cmp::Reverse(x)`
- [ ] Использовать конструктор `BinaryHeap::min_heap()`
- [ ] Вызывать метод `.sort_asc()` перед каждым `.pop()`

**6. Почему двунаправленный связный список `LinkedList<T>` в Rust используется крайне редко?**

- [ ] Узлы аллоцируются в куче отдельно, вызывая частые промахи мимо кэша (Cache Misses)
- [ ] LinkedList запрещен при работе в ночной ветке Rust (Nightly)
- [ ] LinkedList может хранить не более 1024 элементов

**7. Какие типажи (traits) обязательны для типа ключа `K` в `BTreeMap<K, V>`?**

- [ ] Ord (полный порядок)
- [ ] Hash + Eq
- [ ] Copy + Clone

**8. Чем под капотом являются множества `HashSet<T>` и `BTreeSet<T>`?**

- [ ] Тонкими обертками над `HashMap<T, ()>` и `BTreeMap<T, ()>` соответственно
- [ ] Низкоуровневыми битовыми масками
- [ ] Массивами уникальных строк