Создание простого связанного списка

Question

У меня возникли трудности с получением контролера заимствования, работающего на простой итеративный построитель связанных списков.

fn main() {               
    let v = vec![1,5,3,8,12,56,1230,2,1];       
    let nodes = Vec::<Node>::with_capacity(v.len());    
    let mut root: Option<&mut Box<Node>> = None;     
    let mut prev: &Option<&mut Box<Node>> = &None;     

    for i in v {             
     let curr = Some(&mut Box::new(Node { value: i, next: None })); 
     match *prev {            
      Some(ref mut p) => {         
       p.next = curr;           
       prev = &mut p.next;         
      },              
      None => {            
       root = curr;           
       prev = &mut root;         
      }              
     }               
    }                
}                 

struct Node<'a> {             
    value: i32,              
    next: Option<&'a mut Box<Node<'a>>>,       
}       

Ошибки я получаю, когда я пытаюсь скомпилировать:

linked_list.rs:8:30: 8:69 error: borrowed value does not live long enough 
linked_list.rs:8   let curr = Some(&mut Box::new(Node { value: i, next: None })); 
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
note: in expansion of for loop expansion 
linked_list.rs:7:5: 19:6 note: expansion site 
linked_list.rs:4:49: 20:2 note: reference must be valid for the block suffix following statement 2 at 4:48... 
linked_list.rs:4  let mut root: Option<&mut Box<Node>> = None; 
linked_list.rs:5  let mut prev: &Option<&mut Box<Node>> = &None; 
linked_list.rs:6 
linked_list.rs:7  for i in v { 
linked_list.rs:8   let curr = Some(&mut Box::new(Node { value: i, next: None })); 
linked_list.rs:9   match *prev { 
       ... 
linked_list.rs:8:9: 8:71 note: ...but borrowed value is only valid for the statement at 8:8 
linked_list.rs:8   let curr = Some(&mut Box::new(Node { value: i, next: None })); 
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
linked_list.rs:8:9: 8:71 help: consider using a `let` binding to increase its lifetime 
linked_list.rs:8   let curr = Some(&mut Box::new(Node { value: i, next: None })); 
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
linked_list.rs:10:18: 10:27 error: cannot borrow immutable anonymous field `(prev:core::option::Some).0` as mutable 
linked_list.rs:10    Some(ref mut p) => { 
            ^~~~~~~~~ 
note: in expansion of for loop expansion 
linked_list.rs:7:5: 19:6 note: expansion site 
linked_list.rs:15:17: 15:28 error: cannot assign to `root` because it is borrowed 
linked_list.rs:15     root = curr; 
            ^~~~~~~~~~~ 
note: in expansion of for loop expansion 
linked_list.rs:7:5: 19:6 note: expansion site 
linked_list.rs:16:29: 16:33 note: borrow of `root` occurs here 
linked_list.rs:16     prev = &mut root; 
               ^~~~ 
note: in expansion of for loop expansion 
linked_list.rs:7:5: 19:6 note: expansion site 
linked_list.rs:16:29: 16:33 error: cannot borrow `root` as mutable more than once at a time 
linked_list.rs:16     prev = &mut root; 
               ^~~~ 
note: in expansion of for loop expansion 
linked_list.rs:7:5: 19:6 note: expansion site 
linked_list.rs:16:29: 16:33 note: previous borrow of `root` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `root` until the borrow ends 
linked_list.rs:16     prev = &mut root; 
               ^~~~ 
note: in expansion of for loop expansion 
linked_list.rs:7:5: 19:6 note: expansion site 
linked_list.rs:20:2: 20:2 note: previous borrow ends here 
linked_list.rs:1 fn main() { 
... 
linked_list.rs:20 } 
       ^
error: aborting due to 4 previous errors 

То, что я пытаюсь идти довольно просто. Мы перебираем Vec, создавая новый узел на каждой итерации. Если prev является None, это должно быть началом, поэтому мы делаем корневую переменную собственностью этого первого узла. Если это не так, мы обновим следующее значение предыдущего узла, чтобы указать на этот узел.

Я новичок в Rust, поэтому не уверен, где я ошибаюсь. Моя интерпретация заключается в том, что средство проверки займов не справляется с этим. Он не может сделать вывод о том, что ветвь «Нет» в матче, содержащая «корневое» назначение, будет когда-либо вызываться только один раз, в результате чего две ошибки о заимствовании корня дважды. Я прав?

Возможно ли такое использование в ржавчине? Есть ли более идиоматический способ сделать такие вещи?

(Рекурсивный подход, вероятно, гораздо проще, но я хотел бы завершить повторяющийся в качестве учебного упражнения.)

Answer 1

Прежде всего, вы, вероятно, следует убедиться, что вы прочитали и поняли ржавчину книги главы на Ownership и References and Borrowing. Ваша непосредственная проблема заключается в том, что вы заимствуете вещи, которые не являются , принадлежащими ничем, и, таким образом, просто исчезнут. У вас также есть другие проблемы, такие как попытка мутировать через неизменяемый указатель.

Давайте получить что-то, что делает, по крайней мере, работа:

fn main() { 
    let v = vec![1,5,3,8,12,56,1230,2,1]; 
    let mut root: Option<Box<Node>> = None; 

    for i in v.into_iter().rev() { 
     root = Some(Box::new(Node { value: i, next: root })); 
    } 

    println!("root: {}", 
     root.map(|n| n.to_string()).unwrap_or(String::from("None"))); 
} 

struct Node { 
    value: i32, 
    next: Option<Box<Node>>, 
} 

impl std::fmt::Display for Node { 
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> { 
     let mut cur = Some(self); 
     let mut first = true; 
     try!(write!(fmt, "[")); 
     while let Some(node) = cur { 
      if !first { try!(write!(fmt, ", ")); } 
      first = false; 
      try!(write!(fmt, "{}", node.value)); 
      cur = node.next.as_ref().map(|n| &**n); 
     } 
     try!(write!(fmt, "]")); 
     Ok(()) 
    } 
} 

Это создает список и показывает, как можно итеративно отобразить его. Обратите внимание на полное отсутствие заимствований в строительном коде.

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

let v = vec![1,5,3,8,12,56,1230,2,1]; 
let mut v = v.into_iter(); 

let mut root: Option<Box<Node>> = None; 
if let Some(i) = v.next() { 
    root = Some(Box::new(Node { value: i, next: None })); 
    let mut prev: &mut Box<Node> = root.as_mut().unwrap(); 

    for i in v { 
     let curr = Some(Box::new(Node { value: i, next: None })); 
     prev.next = curr; 
     prev = prev.next.as_mut().unwrap(); 
    } 
} 

Вы все еще оказаться в ситуации, когда компилятор видит вас мутируя вещь, которую вы заимствовали по второму пути. Это недостаточно хорошо, чтобы понять, что переназначение prev не фактически создает любые псевдонимы. С другой стороны, если вы разорвать петлю в эквивалент рекурсии:

if let Some(i) = v.next() { 
    root = Some(Box::new(Node { value: i, next: None })); 

    fn step<It>(prev: &mut Box<Node>, mut v: It) where It: Iterator<Item=i32> { 
     if let Some(i) = v.next() { 
      let curr = Some(Box::new(Node { value: i, next: None })); 
      prev.next = curr; 
      step(prev.next.as_mut().unwrap(), v) 
     } 
    } 

    step(root.as_mut().unwrap(), v); 
} 

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

Я сам столкнулся с этой проблемой; петли и &mut указатели не всегда хорошо сочетаются друг с другом. Вы можете обойти это, переключившись на RefCell со своей связанной стоимостью во время выполнения, хотя это и усложняет повторение такого списка в цикле.Другой альтернативой является использование usize s вместо указателей и все узлы, назначенные в Vec, хотя и вводят ограничения на проверку границ.

В противном случае существует код unsafe, который позволяет вам писать более или менее точно то, что вы могли бы написать на другом языке, таком как C или C++, но без обычных гарантий безопасности Rust.

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