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

Сегодня рассмотрим коллекции, которые присутствуют в стандартной библиотеке Rust. Но сначала пару слов о внутреннем устройстве коллекций. Коллекция как группа элементов, которую можно хранить в переменной, должна иметь одну точку входа, через которую мы можем обращаться к ее элементам, например, по индексу. Если мы говорим про массив (Array), то это имя массива, которое представляет из себя указатель на начало массива (место в памяти), расположенного в стеке, все элементы которого располагаются друг за другом, чтобы позволить переходить от одного элемента к другому с шагом равным размеру типа элементов, индекс в данном случае это просто количество шагов от начала массива. Это самый быстрый тип коллекций, он располагается в стеке, что накладывает определенные ограничения, главное из них то, что массив не может менять свою длину.

Если нам нужно менять длину коллекции, то мы можем использовать вектор (Vector), его точка входа размещается в стеке, а его элементы в куче. С виду все также как при работе с массивом, но на самом деле внутри происходит динамическое выделение памяти при добавлении новых элементов и очистка при их удалении, что накладывает дополнительные расходы при работе с векторами. Элементы также располагаются друг за другом в куче, чтобы ускорить к ним доступ по индексу. Также добавление в конец вектора происходит быстро (если мы резервировали место), но если мы захотим вставить элемент в середину вектора, то это потребует смещения последующих за ним элементов, а вставка в начало, потребует смещения всего вектора, это тоже накладные расходы.

Если нам нужно часто делать вставки в начало или конец, то мы можем использовать коллекцию под названием очередь (Queues), она устроена как циклически замкнутый буфер, со свободным местом между его началом и концом. За счет этого вставка элементов в начало или конец происходит очень быстро, путем добавления новых элементов без смещения. Вставка и удаление в середину очереди проигрывает вектору.

Если нам нужно делать много вставок в середину, то мы можем использовать коллекцию под названием связанный список(LinkedList). Где элементы хранятся не друг за другом, а в разных местах кучи. Элементы помимо значений, хранят указатель на область памяти, в которой хранится следующий элемент, это для односвязного списка. Для двусвязного списка хранится также указатель на предыдущий элемент, что позволяет переходить по коллекции в обоих направления, вперед и назад, но такое прохождение очень неоптимальное по перфу, так как переходы происходят по указателям. Вставка и удаление единичных элементов в середину происходит быстро, путем добавления новых указателей в цепочку. Но если нужно вставлять или удалять группу элементов или проходить по длинному списку от начала или конца, то (почти всегда!) лучше использовать вектор или очередь. В стандартной библиотеке Rust есть методы, которые позволяют вставлять в начало и конец списка, но нет методов, которые позволяют вставлять в середину (они пока не стабилизированы). При необходимости их потребуется писать вручную, например используя итератор.

Рекомендуется делать выбор в сторону той или иной коллекции на основании замеров скорости их работы. Также есть еще несколько типов коллекций, позволяющих хранить отсортированные элементы, без повторяющихся элементов, и в виде словарей, где элементы представляют из себя пары ключ-значение. Про них поговорим следующий раз.

fn main() {
    const SIZE: usize = 3;
    //Vector init
    let vec0: Vec<i32> = vec![]; //empty
    let vec1 = vec![1, 2, 3]; //1,2,3
    let mut vec2 = vec![0; 3]; //0,0,0
    let vec3: Vec<i32> = Vec::new(); //empty
    let vec4 = Vec::<i32>::new(); //empty
    let mut vec5 = Vec::<i32>::with_capacity(SIZE); //empty
    println!("{:?}", vec5); //[]
    //Clearing
    vec2.clear();
    println!("{:?}", vec2); //[]
    //Check if it contains particular element
    if vec1.contains(&2){
        println!("{:?} contains 2", vec1); //[1, 2, 3] contains 2
    }
    //Add element
    for i in 0..SIZE {
        vec5.push(i as i32);
    }
    //Length
    println!("{:?}", vec5.len()); //3
    //Iterating immutable
    for element in vec5.iter() {
        print!("{:?} ", *element); //0 1 2
    }
    //Iterating mutable
    for element in vec5.iter_mut() {
        *element += 1;
    }
    println!("{:?}", vec5); //[1,2,3]
    //Popping from the end
    for _ in 0..3 {
        println!("{:?}", vec5.pop().unwrap()); //3 2 1
    }
    println!("{:?}", vec5.len()); //0
    //Inserting
    for i in 0..SIZE {
        vec5.insert(0, i as i32);
    }
    println!("{:?}", vec5); //[2,1,0]
    //Sorting
    vec5.sort();
    println!("{:?}", vec5); //[0,1,2]
    //Removing
    for _ in 0..SIZE {
        vec5.remove(0);
    }
    println!("{:?}", vec5); //[]
    //Check if it is empty
    if vec5.is_empty(){
        println!("{:?} is empty", vec5); //[] is empty
    }

    //VecDeque init
    let vec_deq = std::collections::VecDeque::from(vec5.clone());
    let mut vec_deq = std::collections::VecDeque::<i32>::new();
    //Add element to the end
    for i in 0..vec1.len() {
        vec_deq.push_back(i as i32);
    }
    println!("{:?}", vec_deq); //[0,1,2]
    //Popping from the begin
    while vec_deq.len() > 0 {
        vec_deq.pop_front();
    }
    println!("{:?}", vec_deq.len()); //0
    vec_deq.insert(0,5);
    println!("{:?}", vec_deq); //[5]
    vec_deq.remove(0);
    println!("{:?}", vec_deq); //[]

    //LinkedList init
    let mut list = std::collections::LinkedList::<i32>::new();
    list.push_front(0);
    list.push_front(1);
    println!("{:?}", list); //[1,0]
    //Iterate
    let mut iter = list.iter_mut();
    *iter.next().unwrap() = 2;
    println!("{:?}", list); //[2,0]
    println!("{:?}", list.len()); //2
    //References to the front and to the back
    println!("front: {:?}, back: {:?}", list.front().unwrap(), list.back().unwrap()); //front: 2, back: 0

}

Перегуд В.