Collections

HashMap & BTreeMap
Rust HashMap and BTreeMap collections
HashSet & BTreeSet
Rust HashMap and BTreeMap collections
Vectors
Rust vectors

Сравнение коллекций

Коллекция	Доступ по индексу	Вставка	Поиск	Память
`Vec`	O(1)	O(1) аморт.*	O(n)	Непрерывная
`String`	O(1) (по байтам)	O(1) аморт.*	O(n)	Непрерывная
`HashMap`	—	O(1) в среднем	O(1) в среднем	Разбросанная
`HashSet`	—	O(1) в среднем	O(1) в среднем	Разбросанная

*Амортизированная O(1) — в среднем быстрая, но может быть O(n) при перевыделении памяти.

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

HashMap & BTreeMap

Hashmap<K, V, S = RandomState>

Это изменяемая структура словарь (“dictionary” в Python), которая хранит пары “ключ->значение”. В Rust Prelude она не входит, макроса создания не имеет. Поэтому нужно указывать библиотеку явно и явно создавать структуру.

use std::collections::HashMap;  
  
fn main() {  
    let mut scores = HashMap::new();  
    scores.insert(String::from("Alpha"),1);  
    scores.insert(String::from("Beta"),2);  
    scores.insert(String::from("Gamma"),3); 
}

Все ключи Hashmap должны быть уникальны и одного типа, все значения должны быть одного типа.

Warning

Значения с кучи типа String перемещаются (move) в Hashmap, который становится их владельцем.

Взятие значения по ключу из Hashmap с помощью get нужно сопровождать проверкой - есть ли в памяти запрашиваемые ключ и значение:

let name = String::from("Gamma");  
if let Some(letter_num) = scores.get(&name) {  
    println!("{}",letter_num);  
} else { println!("Value not in HashMap!"); }

Итерация по Hashmap похожа на итерацию по вектору:

for (key, value) in &scores {  
    println!("{key} -> {value}"); }

Обновление Hashmap

Есть ряд стратегий обновления значений в Hashmap:

Перезаписывать всегда

scores.insert(String::from("Gamma"),3); // вставка дважды значений по одному 
scores.insert(String::from("Gamma"),6); // ключу сохранит последнее значение

Записывать значение, если у ключа его нет:

scores.entry(String::from("Delta")).or_insert(4); // entry проверяет наличие
// значения, or_insert возвращает mut ссылку на него, либо записывает новое 
// значение и возвращает mut ссылку на это значение.

Записывать значение, если ключа нет. Если же у ключа есть значение, модифицировать его:

use std::collections::HashMap;

let mut map: HashMap<&str, u32> = HashMap::new();

map.entry("poneyland") // первое добавление
   .and_modify(|e| { *e += 1 })
   .or_insert(42);     // добавит ключ "poneyland: 42"
assert_eq!(map["poneyland"], 42);

map.entry("poneyland") // второе добавление найдёт ключ со значением
   .and_modify(|e| { *e += 1 }) // и модифицирует его
   .or_insert(42);
assert_eq!(map["poneyland"], 43);

Записывать значение, если ключа нет, в виде результата функции. Эта функция получает ссылку на значение ключа key, который передаётся в .entry(key):

use std::collections::HashMap;

let mut map: HashMap<&str, usize> = HashMap::new();
map
  .entry("poneyland")
  .or_insert_with_key(|key| key.chars().count());

assert_eq!(map["poneyland"], 9);

Поднимать старое значение ключа, проверять его перед перезаписью:

let text = "hello world wonderful world";  
let mut map = HashMap::new();  
  
for word in text.split_whitespace() {  
    let count = map.entry(word).or_insert(0);  
    *count += 1;  
}  

println!("{:?}",map); // {"wonderful": 1, "hello": 1, "world": 2}

Инициализация HashMap со значениями по-умолчанию

Поведение аналогично типу defaultdict в Python. Заполнять ключами HashMap:

в случае отсутствия ключа, создавать его со значением по-умолчанию (0);
в случае присутствия ключа, добавлять к значению +1. Аналогичный подход реализуется с fold(), а также с помощью itertools::counts() :

use std::collections::HashMap;
pub fn main() {
    let num_vec = vec![1, 2, 1, 3, 5, 2, 1, 4, 6];
    let mut number_count: HashMap<i32, i32> = HashMap::new();
    for key in num_vec {
        *number_count.entry(key).or_default() += 1;
    }
    for (k, v) in number_count {
        print!("{} -> {}; ", k, v);
    }
}
// 4 -> 1; 1 -> 3; 2 -> 2; 6 -> 1; 5 -> 1; 3 -> 1;

Метод entry позволяет избежать проверки contains_key вручную.

Более простой аналог с for_each():

let mut number_count = HashMap::new();
num_vec.iter().for_each(|s| {
    *number_count.entry(s).or_insert(0) += 1;
});

Удаление элемента

use std::collections::HashMap;

let mut map: HashMap<&str, i32> = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);
map.remove("b"); // удаляет по ключу "b"
println!("{:?}", map); // {"a": 1, "c": 3}

Альтернатива: Если не нужно сдвигать элементы, можно использовать .swap_remove(index) (быстрее, O(1), но меняет порядок):

let mut numbers = vec![1, 2, 3, 4];
numbers.swap_remove(1); // заменяет на последний элемент и удаляет его
println!("{:?}", numbers); // [1, 4, 3]

Сортировка HashMap

Если нужно отсортировать по значениям придётся:

Преобразовать HashMap в вектор пар (ключ, значение);
Отсортировать его;
Собрать обратно (если нужно).

use std::collections::HashMap;

let mut hmap: HashMap<&str, i32> = HashMap::from([
    ("b", 3),("a", 1),("c", 2),]);
let mut hsorted = hmap.into_iter().collect::<Vec<(&str, i32)>>();
hsorted.sort_by(|a, b| a.1.cmp(&b.1)); // сортировка по значению
println!("{:?}", hsorted); // [("a", 1), ("c", 2), ("b", 3)]

BTreeMap<K, V, A = Global>

Упорядоченная по ключам K структура данных на основе B-дерева. Ключевые отличия от HashMap:

Свойство	HashMap	BTreeMap
Внутренняя структура	Хэш таблица	Дерево поиска
Упорядоченность	Не гарантированная	Ключи всегда упорядочены
Скорость	O(1)	O(log n)
Требования	`Hash + Eq`	`Ord`
Потребление памяти	Выше	Ниже

Применение

Когда нужно сразу сортировать данные:

    let mut scores = BTreeMap::new();
    scores.insert("Charlie", 85);
    scores.insert("Alice", 92);
    scores.insert("Bob", 78);

    // Итерация сразу в отсортированном порядке по ключам
    for (name, score) in &scores {
        println!("{}: {}", name, score); // Alice, Bob, Charlie
    }

    // Получить 1ый и последний элементы
    println!("{:?}", scores.first_key_value()); // ("Alice", 92)
    println!("{:?}", scores.last_key_value()); // ("Charlie", 85)

Работа с диапазонами значений:

    // Диапазоны заданы кортежами (нижняя_граница, верхняя_граница)
    let mut price_ranges = BTreeMap::new();
    price_ranges.insert((0, 10), "Budget");
    price_ranges.insert((11, 50), "Standard");
    price_ranges.insert((51, 100), "Premium");
    price_ranges.insert((101, 1000), "Luxury");

    let query_price = 42;

    // Поиск по диапазонам (линейный в данном случае)
    for ((low, high), category) in &price_ranges {
        if query_price >= *low && query_price <= *high {
            println!(
                "Price ${} is in category: {} (range: {}-{})",
                query_price, category, low, high
            );
            break;
        } }

Порядок при сериализации в JSON:

use serde_json 

let mut config = BTreeMap::new();
config.insert("zebra", "animal");
config.insert("apple", "fruit");
config.insert("banana", "fruit");

// сериализация в JSON с порядком элементов
let json = serde_json::to_string_pretty(&config).unwrap();
println!("{}", json); // ключи будут в порядке: apple, banana, zebra

Сравнение HashMap vs BTreeMap по скорости

use std::collections::{BTreeMap, HashMap};
use std::time::Instant;

fn main() {
    let n = 100_000;
    
    // HashMap insertion
    let start = Instant::now();
    let mut hash_map = HashMap::new();
    for i in 0..n {
        hash_map.insert(i, i * 2);
    }
    println!("HashMap insert: {:?}", start.elapsed());

    // BTreeMap insertion
    let start = Instant::now();
    let mut btree_map = BTreeMap::new();
    for i in 0..n {
        btree_map.insert(i, i * 2);
    }
    println!("BTreeMap insert: {:?}", start.elapsed());
}
// HashMap insert: 50.855881ms
// BTreeMap insert: 102.619694ms

Для небольших коллекций (< 1000 элементов) или когда требуется отсортированный порядок, BTreeMap часто предпочтительнее. Для больших коллекций, где нужна максимальная скорость, а порядок не имеет значения, HashMap обычно лучше.

HashSet & BTreeSet

Оба типа представляют множества для хранения уникальных элементов.

Отличия HashSet и BTreeSet

Множество	HashSet	BTreeSet
Сортировка	Случайный порядок	Да
Сложность алгоритма	O(1) в среднем	O(log n)
Потребление памяти	Выше (hash-таблица)	Ниже
Запросы диапазонов значений	Нет	Да
Типажи	`T: Hash + Eq`	`T: Ord`

Работа с HashSet

use std::collections::HashSet;

fn main() {
    // Создание
    let mut colors = HashSet::new();
    
    // Добавление элеметов
    colors.insert("red");
    colors.insert("green");
    colors.insert("blue");
    colors.insert("red"); // дубликат - не будет добавлен!
    
    println!("HashSet: {:?}", colors); // порядок произвольный
    
    // Проверка существования элемента
    if colors.contains("green") {
        println!("Contains green!");
    }
    
    // Итерация (порядок не гарантирован)
    for color in &colors {
        println!("Color: {}", color);
    }
    
    // Удаление элемента
    colors.remove("blue");
    
    // Объединение двух HashSet
    let mut warm_colors = HashSet::new();
    warm_colors.insert("red");
    warm_colors.insert("yellow");
    warm_colors.insert("orange");
    
    let all_colors: HashSet<_> = colors.union(&warm_colors).collect();
    println!("All colors: {:?}", all_colors);
}

Работа с BTreeSet

use std::collections::BTreeSet;

fn main() {
    // Создание BTreeSet
    let mut numbers = BTreeSet::new();
    
    // Вставка элементов (авто-сортировка!)
    numbers.insert(5);
    numbers.insert(2);
    numbers.insert(8);
    numbers.insert(1);
    numbers.insert(5); // дубликат - не будет добавлен!
    
    println!("BTreeSet: {:?}", numbers); // сортировка всегда: {1, 2, 5, 8}
    
    // Проверка существования элемента
    if numbers.contains(&2) {
        println!("Contains 2!");
    }
    
    // Итерация по порядку
    for num in &numbers {
        println!("Number: {}", num); // 1, 2, 5, 8
    }
    
    // Получить первый и последний элементы
    if let Some(first) = numbers.first() {
        println!("First element: {}", first); // 1
    }
    
    if let Some(last) = numbers.last() {
        println!("Last element: {}", last); // 8
    }
    
    // Запрос диапазона значений
    let range: Vec<_> = numbers.range(2..=5).collect();
    println!("Numbers between 2 and 5: {:?}", range); // [2, 5]
    
    // Удаление элемента
    numbers.remove(&5);
}

HashSet -> Vector

Простой способ:

use std::collections::HashSet;

let set: HashSet<char> = ['a', 'b', 'c', 'd'].into_iter().collect();
// Перевод в Vec<char> - расстановка элементов произвольная
let vec: Vec<char> = set.into_iter().collect();
println!("Vec: {:?}", vec); // Example: ['c', 'a', 'd', 'b']

С сохранением исходного HashSet:

let vec: Vec<char> = set.iter().cloned().collect();

Vectors

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

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

Методы

// Задание пустого вектора:
// let mut a test_vector: Vec<i32> = Vec::new();  

// Задание вектора со значениями через макрос:
let mut test_vector = vec![1, 2, 3, 4];  

test_vector.push(42);  // добавить число 42 в конец mut вектора
let Some(last) = test_vector.pop(); // удаляет и возвращает последний элемент (возвращает Option<T>)
test_vector.remove(0);  // удалить первый элемент =1
  
for i in &mut test_vector {  // пройти вектор как итератор для вывода
*i += 1; // изменять значения при их получении требует делать '*' dereference
println!("{i}"); }

println!("Vector length: {}", test_vector.len()); // количество элементов

extend() - расширить вектор с помощью итератора:

let mut test_vector = vec![1, 2, 3, 4];
test_vector.extend([5, 6, 7, 8].iter());
println!("{:?}", test_vector); // [1, 2, 3, 4, 5, 6, 7, 8]

chain() - соединяет 2 итератора вместе, элементы второго после всех элементов первого:

let test_vector = [1, 2, 3, 4];
let test_vector = test_vector
    .iter()
    .chain([5, 6, 7, 8].iter())
    .collect::<Vec<&i32>>();
println!("{:?}", test_vector); // [1, 2, 3, 4, 5, 6, 7, 8]

Получение элемента вектора

Элемент можно получить либо с помощью индекса, либо с помощью безопасного метода get:

let mut test_vector = vec![1,2,3,4,5];  
println!("Third element of vector is: {}", &test_vector[2]);  // индекс
  
let third: Option<&i32> = test_vector.get(2);  // безопасный метод get
match third {  
    Some(third) => println!("Third element of vector is: {}", third),  
    None => println!("There is no third element")  
}

Разница в способах в реакции на попытку взять несуществующий элемент за пределами вектора. Взятие через индекс приведёт к панике и остановке программы. Взятие с помощью get сопровождается проверкой и обработкой ошибки.

Удаление элемента

Метод .remove(index):

let mut numbers = vec![1, 2, 3, 4];
numbers.remove(1); // удаляет элемент с индексом 1
println!("{:?}", numbers); // [1, 3, 4]

.remove() сдвигает все последующие элементы, что может быть дорого для больших векторов (O(n));
Возвращает удалённый элемент;
Требует mut, так как изменяет вектор;
Индекс должен быть в пределах длины, иначе паника.

Хранение элементов разных типов в векторе

Rust нужно заранее знать при компиляции, сколько нужно выделять памяти под каждый элемент. Если известны заранее все типы для хранения, то можно использовать промежуточный enum:

#[derive(Debug)]  
enum SpreadSheet {  
    Int(i32),  
    Float(f64),  
    Text(String)  
}  
  
fn main() {  
    let row = vec![  
      SpreadSheet::Int(42),  
      SpreadSheet::Float(3.14),  
      SpreadSheet::Text(String::from("red"))  
    ];  
  
    for i in row {  
        println!("{:?}",i);  
    }  }

Vector со строками String

let mut v: Vec<String> = Vec::new();

Пустой вектор с нулевыми строками можно создать через Default размером до 32 элементов (Rust 1.47):

let v: [String; 32] = Default::default();

Вектор большего размера можно создать через контейнер Vec:

let mut v: Vec<String> = vec![String::new(); 100];

Вектор с заданными строками можно инициализировать либо с помощью метода to_string(), либо через определение макроса:

macro_rules! vec_of_strings {
    ($($x:expr),*) => (vec![$($x.to_string()),*]);
}

fn main()
{
    let a = vec_of_strings!["a", "b", "c"];
    let b = vec!["a".to_string(), "b".to_string(), "c".to_string()];
    assert!(a==b); // True
}

Соединение вектора со строками в строку (Join):

result_vec.join(" "); // указывается разделитель для соединения
// в старых версиях Rust <1.3 применяют метод .connect();

Сортировка

let number_vector = vec!(1,12,3,1,5);   
number_vector.sort(); // 1,1,3,5,12

Способы реверс-сортировки

Смена элементов при сравнении, метод .sort_by() принимает замыкание (closure) для пользовательской сортировки:

number_vector.sort_by(|a,b| b.cmp(a));

|a, b| — это замыкание;
b.cmp(a) возвращает порядок: Ordering::Less, Equal или Greater. Инверсия (b.cmp(a) вместо a.cmp(b)) даёт убывающий порядок. Альтернатива: .sort_by_key() для сортировки по вычисляемому ключу:

let mut numbers = vec![3, 1, 4, 1, 5];
numbers.sort_by_key(|&x| -x); // по убыванию через отрицание
println!("{:?}", numbers); // [5, 4, 3, 1, 1]

Сортировка, потом реверс:

number_vector.sort();
number_vector.reverse();

Обёртка Reverse с экземпляром Ord:

use std::cmp::Reverse;
number_vector.sort_by_key(|w| Reverse(*w));

Если вернуть Reverse со ссылкой и без *, это приведёт к проблеме с временем жизни.

Сортировка вектора по ключу

use std::collections::HashSet;

fn main() {
    let mut vowels = HashSet::new();
    vowels.insert('e');
    vowels.insert('a');
    vowels.insert('i');
    vowels.insert('o');
    vowels.insert('u');
    
    // Конвертация в Vec и сортировка
    let mut vowel_vec: Vec<char> = vowels.into_iter().collect();
    // Свой порядок сортировки: a, e, i, o, u
    let vowel_order = |c: &char| match c {
        'a' => 0,
        'e' => 1,
        'i' => 2,
        'o' => 3,
        'u' => 4,
        _ => 5,
    };
    
    vowel_vec.sort_by_key(vowel_order);
    println!("Sorted vowels: {:?}", vowel_vec); // ['a', 'e', 'i', 'o', 'u']
}

Дедупликация вектора

Удаление одинаковых элементов в векторе, похоже на работу с HashSet.

let s = "aabbccdddeeeeffffeee";
let mut chars: Vec<char> = s.chars().collect();
// Сначала отсортировать, чтобы собрать одинаковые элементы вместе
chars.sort_unstable(); 
// dedup() удаляет на месте одинаковые СТОЯЩИЕ РЯДОМ в векторе элементы
chars.dedup();
// собрать назад в String:
let unique_s: String = chars.into_iter().collect();

Получение вектора из итератора

    let collected_iterator: Vec<i32> = (0..10).collect();
    println!("Collected (0..10) into: {:?}", collected_iterator);
    // Collected (0..10) into: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Конвертация

Конвертация из массива array в vector:

let number_list = [1,12,3,1,5,2];  
let number_vector = number_list.to_vec(); // перевод array[i32] -> vector<i32>

Вариант через итератор:

let a = [10, 20, 30, 40]; 
let v: Vec<i32> = a.iter().map(|&e| e as i32).collect();

Вектор из байтов vector of bytes в строку String:

use std::str;

fn main() {
    let buf = &[0x41u8, 0x41u8, 0x42u8]; // vector of bytes
    let s = match str::from_utf8(buf) {
        Ok(v) => v,
        Err(e) => panic!("Invalid UTF-8 sequence: {}", e),
    };
    println!("result: {}", s);
}

Collections

Сравнение коллекций

Subsections of Collections

HashMap & BTreeMap

Hashmap<K, V, S = RandomState>

Обновление Hashmap

Инициализация HashMap со значениями по-умолчанию

Удаление элемента

Сортировка HashMap

BTreeMap<K, V, A = Global>

Применение

Сравнение HashMap vs BTreeMap по скорости

HashSet & BTreeSet

Отличия HashSet и BTreeSet

Работа с HashSet

Работа с BTreeSet

HashSet -> Vector

Vectors

Vectors

Методы

Получение элемента вектора

Удаление элемента

Хранение элементов разных типов в векторе

Vector со строками String

Сортировка

Способы реверс-сортировки

Сортировка вектора по ключу

Дедупликация вектора

Получение вектора из итератора

Конвертация