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

2018-11-13

Learning Rust With Entirely Too Many Linked Lists

Оригиналния източник: http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html

Пълния код: 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, Link::Empty)

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/main_0.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/main_0.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_0`
  |
  = note: consider adding a `main` function to `/src/main_0.rs`

error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
 --> /src/main_0.rs:1:6
  |
1 | impl<'a, T> Iterator for Iter<'a, T> {
  |      ^^ unconstrained lifetime parameter

error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predicates
 --> /src/main_0.rs:1:10
  |
1 | impl<'a, T> Iterator for Iter<'a, T> {
  |          ^ unconstrained type parameter

error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
  --> /src/main_0.rs:11:6
   |
11 | impl<'a, T> Iterator for IterMut<'a, T> {
   |      ^^ unconstrained lifetime parameter

error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predicates
  --> /src/main_0.rs:11:10
   |
11 | impl<'a, T> Iterator for IterMut<'a, T> {
   |          ^ unconstrained type parameter

Итерация по 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]: use of moved value: `*first_ref`
 --> /src/main_13.rs:7:5
  |
5 |     let second_ref = first_ref;
  |         ---------- value moved here
6 | 
7 |     first_ref.push_str(" bar");
  |     ^^^^^^^^^ value used here after move
  |
  = note: move occurs because `first_ref` has type `&mut std::string::String`, which does not implement the `Copy` trait

Итерация по 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

Тук не става въпрос за преместване или копиране на 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 рано в метода и оттам нататък да работите безопасно с нея.

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

Въпроси