Свързани списъци, част 1

19 ноември 2019

Learning Rust With Entirely Too Many Linked Lists

Оригиналния източник: https://rust-unofficial.github.io/too-many-lists/

Пълния код: https://github.com/rust-unofficial/too-many-lists/tree/master/lists

Тези слайдове ще съдържат само кратки обобщения на интересни части от кода.

std::mem::replace

Удобна функция, която ни позволява да разменим две стойности:

1 2 3
use std::mem;

let head = mem::replace(&mut self.head, None)

Option::take

По-четим и удобен за използване вариант на предната функция за Option

1 2 3 4 5
let head = self.head.take();

// Превежда се отдолу до:
let head = Option::take(&mut self.head);
let head = std::mem::replace(&mut self.head, None);

Трябва self да е взето или като mut self, или &mut self

map & as_ref

Метода map се използва често когато имаме Option:

1 2 3
pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
}

Map обаче взема ownership! Метода as_ref Конвертира Option<T> в Option<&T>, което ни позволява да достъпим вътрешната стойност по reference (ако изобщо има такава).

Итерация по reference

Итерирането по този начин включва вземане на вътрешния &Node изпод Box-а. Това може да изглежда объркващо…

1 2 3 4 5
pub fn iter(&self) -> Iter<T> {
    Iter {
        current: self.head.as_ref().map(|node| &**node),
    }
}

Винаги трябва да мислим за типовете! В случая имаме:

1 2
Option<Box<Node<T>>> // в списъка.
Option<&Node<T>>     // в итератора. Не искаме Box, защото не искаме ownership

Итерация по reference

1 2 3 4 5 6 7 8
// self.head: Option<Box<Node<T>>>
// current:   Option<&Node<T>>
let current = self.head.as_ref().map(|node| &**node);

//    node: &Box<Node<T>>
//   *node: *&Box<Node<T>> -> Box<Node<T>>
//  **node: *Box<Node<T>> -> *&Node<T> -> Node<T>
// &**node: &Node<T>

Алтернативно, функцията Box::as_ref ни дава същия процес с по-малко perl-like код:

1 2 3 4
let mut current = self.head.as_ref().map(|node| Box::as_ref(node));

// Или, за по-кратко:
let mut current = self.head.as_ref().map(Box::as_ref);

Итерация по mutable reference

1 2 3
let mut current = self.head.as_mut().map(|node| &mut **node);
// Или
let mut current = self.head.as_mut().map(Box::as_mut);

Благодарение на всичките safety check-ове, спокойно можем и да си вземем mutable reference, с почти същия код.

Итерация по mutable reference

Ключова разлика между итерирането по immutable vs mutable reference:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}
error[E0412]: cannot find type `Iter` in this scope --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:1:26 | 1 | impl<'a, T> Iterator for Iter<'a, T> { | ^^^^ not found in this scope help: possible candidates are found in other modules, you can import them into scope | 1 | use std::collections::binary_heap::Iter; | 1 | use std::collections::btree_map::Iter; | 1 | use std::collections::btree_set::Iter; | 1 | use std::collections::hash_map::Iter; | and 8 other candidates error[E0412]: cannot find type `IterMut` in this scope --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:11:26 | 11 | impl<'a, T> Iterator for IterMut<'a, T> { | ^^^^^^^ not found in this scope help: possible candidates are found in other modules, you can import them into scope | 1 | use std::collections::btree_map::IterMut; | 1 | use std::collections::hash_map::IterMut; | 1 | use std::collections::linked_list::IterMut; | 1 | use std::collections::vec_deque::IterMut; | and 3 other candidates error[E0601]: `main` function not found in crate `main_bd89498dcde853512e56e96ce6b1ea86c0580005` --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:1:1 | 1 | / impl<'a, T> Iterator for Iter<'a, T> { 2 | | type Item = &'a T; 3 | | fn next(&mut self) -> Option<Self::Item> { 4 | | self.next.map(|node| { ... | 18 | | } 19 | | } | |_^ consider adding a `main` function to `src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs` error[E0309]: the parameter type `T` may not live long enough --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:2:5 | 1 | impl<'a, T> Iterator for Iter<'a, T> { | - help: consider adding an explicit lifetime bound `T: 'a`... 2 | type Item = &'a T; | ^^^^^^^^^^^^^^^^^^ | note: ...so that the reference type `&'a T` does not outlive the data it points at --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:2:5 | 2 | type Item = &'a T; | ^^^^^^^^^^^^^^^^^^ error[E0309]: the parameter type `T` may not live long enough --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:12:5 | 11 | impl<'a, T> Iterator for IterMut<'a, T> { | - help: consider adding an explicit lifetime bound `T: 'a`... 12 | type Item = &'a mut T; | ^^^^^^^^^^^^^^^^^^^^^^ | note: ...so that the reference type `&'a mut T` does not outlive the data it points at --> src/bin/main_bd89498dcde853512e56e96ce6b1ea86c0580005.rs:12:5 | 12 | type Item = &'a mut T; | ^^^^^^^^^^^^^^^^^^^^^^
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

Итерация по mutable reference

Разликата е в тези два реда:

1 2 3 4
// immutable:
self.next.map(|node| {
// mutable:
self.next.take().map(|node| {

Защо е нужно да викнем take? В първия случай, self.next е от тип Option<&Node>, докато във втория e Option<&mut Node>.

Итерация по mutable reference

Викането на self.next.map в първия случай прави копие на този option, понеже типа &T, за което и да е T, е Copy. Това е смислено, понеже можем да имаме колкото си искаме immutable references към нещо.

Типа &mut T не е Copy, обаче. Това не се компилира, защото mutable reference-а има move semantics:

1 2 3 4 5 6 7 8 9
fn main() {
    let mut source = String::from("foo");

    let first_ref = &mut source;
    let second_ref = first_ref;

    first_ref.push_str(" bar");
    println!("{}", second_ref);
}
error[E0382]: borrow of moved value: `first_ref` --> src/bin/main_0767fd34d56f3e7809af0124610fe055577d7d22.rs:7:5 | 4 | let first_ref = &mut source; | --------- move occurs because `first_ref` has type `&mut std::string::String`, which does not implement the `Copy` trait 5 | let second_ref = first_ref; | --------- value moved here 6 | 7 | first_ref.push_str(" bar"); | ^^^^^^^^^ value borrowed here after move
fn main() {
    let mut source = String::from("foo");

    let first_ref = &mut source;
    let second_ref = first_ref;

    first_ref.push_str(" bar");
    println!("{}", second_ref);
}

Итерация по mutable reference

Това, от друга страна, се компилира без проблеми, защото immutable references се копират:

1 2 3 4 5 6 7 8 9
fn main() {
    let source = String::from("foo");

    let first_ref = &source;
    let second_ref = first_ref;

    println!("{}", first_ref);
    println!("{}", second_ref);
}
foo foo
fn main() {
    let source = String::from("foo");

    let first_ref = &source;
    let second_ref = first_ref;

    println!("{}", first_ref);
    println!("{}", second_ref);
}

Тук не става въпрос за преместване или копиране на source, а за references към source! И references са някакви конкретни типове, алокирани на стека, и за тях може да се мисли дали ще се копират или ще се преместват.

Не е нужно да се ползва map

Тези три имплементации на peek са еквивалентни:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
}

pub fn peek(&self) -> Option<&T> {
    match self.head {
        None => None,
        Some(ref node) => Some(&node.elem)
    }
}

pub fn peek(&self) -> Option<&T> {
    let node = self.head.as_ref()?;
    Some(&node.elem)
}

Не е нужно да се ползва map

Дали ще ползвате map, експлицитен pattern-matching, или ? оператора е предимно въпрос на предпочитание. Не всички варианти са използваеми на всички места, разбира се.

Напълно е възможно да започнете с експлицитен pattern-matching, и да видите, че можете да си опростите кода значително с един map. Или да "извадите" стойност от option рано в метода и оттам нататък да работите безопасно с нея.

Експериментирайте, за да откриете с какво се чувствате най-комфортни. Правете го редовно -- силно е вероятно предпочитанията ви да се променят с времето.

Въпроси