Коллекции в Rust. Часть 2.

Продолжаем про коллекции в Rust. Есть такое понятие, как приоритетная очередь (priority queue), ее можно зафейкать для вектора (Vector), если организовать сортировку элементов по какому-нибудь признаку, например, по большему значению элементов для простых типов или по какому-нибудь полю структуры, если это пользовательский тип. Как мы уже узнали, такая операция может обойтись нам очень дорого, так как потребуется перемещение элементов внутри массива, и бывает дешевле, если создать массив с нужной последовательностью заново. Часто нам нужно даже не иметь отсортированный вектор (вся последовательность элементов), а именно элемент удовлетворяющий нашему условию, в частности наибольший элемент и желательно, чтобы его можно было получить с наибольшей скоростью, т.е. организовать эффективный поиск (бинарный) – получить наибольший элемент, без полной сортировки, так мы сэкономим ресурсы. И в этом нам поможет коллекция из стандартной библиотеки BinaryHeap. Чтобы элементы такой коллекции могли быть отсортированы, они должны как минимум имплементировать характеристики PartialOrd и PartialEq. Базовые типы имплементируют их из коробки, для пользовательских нужно определить, что мы и сделали в статье Обобщенные типы в Rust.

Следующие коллекции, которые мы рассмотрим, это наборы данных (sets). В математике их называют множества, отличительная их особенность заключается в том, что они содержат данные без повторов, т.е. если мы добавляем элемент, который уже присутствует в коллекции, то в зависимости от наших потребностей, он либо перезаписывает имеющийся, либо не добавляется. Наборы данных бывают двух видов. Первый - несортированные (unordered sets) элементы хранятся в случайном порядке, такой набор можно создать с помощью коллекции HashSet. Второй – отсортированные по значению (ordered sets), такой набор можно создать с помощью коллекции BTreeSet.

Последние коллекции, про которые мы поговорим, это словари (dictionaries). Словари представляют из себя наборы данных (sets), для которых, в качестве элементов используются пары ключ-значение (key-value). В результате чего в словаре не может быть больше одной пары с одинаковым ключом. И наоборот, допускается иметь несколько пар с одинаковым значением. При добавлении пары с существующим ключом, происходит перезапись старого значения. В словарях обращение к элементу происходит не по порядковому номеру всей пары (индексу), а только по ключу (key). Словари также бывают двух видов. Первый вид – несортированные (unordered dictionaries) элементы хранятся в случайном порядке, такой набор можно создать с помощью коллекции HashMap. Второй вид – отсортированные по ключу (ordered dictionaries), такой набор можно создать с помощью коллекции BTreeMap. Пары задаются с помощью кортежа (tuple), который в последствии можно деструктурировать в переменные key и value. Смотрим пример.

fn main() {
    const SIZE: usize = 3;
    //BinaryHeap init
    let mut priority_queue = std::collections::BinaryHeap::<i32>::new();
    //Add elements
    priority_queue.push(3);
    priority_queue.push(1);
    priority_queue.push(2);
    println!("{:?}", priority_queue); //[3, 1, 2]
    //Popping
    while !priority_queue.is_empty() {
        println!("{:?}", priority_queue.pop().unwrap()); //3 2 1
    }

    //Sets init
    let mut hash_set = std::collections::HashSet::<_>::new();
    let mut btree_set = std::collections::BTreeSet::<_>::new();
    //Add element
    for _ in 0..3 {
        hash_set.insert(2); //2,2,2
        hash_set.insert(1); //2,2,2,1,1,1
        btree_set.insert(2); //2,2,2
        btree_set.insert(1); //2,2,2,1,1,1
    }
    println!("{:?}", hash_set); //{2,1} random
    println!("{:?}", btree_set); //{1,2} ordered

    //Dictionaries init
    let mut hash_map = std::collections::HashMap::<_, _>::new();
    let mut btree_map = std::collections::BTreeMap::<_, _>::new();
    let tmp_arr = [(5, 'Z'), (1, 'X'), (2, 'V'), (3, 'Z'), (1, 'Y')];
    //Add element
    for &(key, value) in tmp_arr.iter() { //destructuring
        hash_map.insert(key, value);
        btree_map.insert(key, value);
    }
    println!("{:?}", hash_map); //{1: 'Y', 2: 'V', 5: 'Z', 3: 'Z'} random
    println!("{:?}", btree_map); //{1: 'Y', 2: 'V', 3: 'Z', 5: 'Z'} ordered
    let to_find = [3, 5];
    for num in &to_find {
        match hash_map.get(num) {
            Some(character) => println!("{},{}", num, character), //3,Z 5,Z
            None => println!("key {} does not exist", num),
        }
    }
    if btree_map.contains_key(&5) {
        println!("key 5 exists")
    }
    // insert a key only if it doesn't already exist
    btree_map.entry(4).or_insert('X');
    println!("{:?}", btree_map); //{1: 'Y', 2: 'V', 3: 'Z', 4: 'X', 5: 'Z'}
    for val in btree_map.values() {
        println!("{}", val); //Y, V, Z, X, Z
    }
    for val in btree_map.keys() {
        println!("{}", val); //1, 2, 3, 4, 5
    }
    println!("{:?}", btree_map.get_key_value(&1).unwrap()); //(1,'Y')
}

Перегуд В.