不使用标准库时如何迭代搜索并从列表中删除

Question

我正在尝试编写一个没有递归的简单循环来遍历 Rust 列表（第一个节点是哨兵）并从中删除一个元素（不是哨兵）。

我已经成功地编写了一个 remove_first 函数，它可以独立运行，但是尝试遍历列表导致借用检查器出现问题：

程序如下：

// This code is placed in the public domain
struct Node<'a> {
    val : i32,
    next : Option<&'a mut Node<'a> >,
}
struct List<'a> {
    glob : Option<&'a mut Node<'a> >,
}


struct AllocatedList<'a> {
   el0 : Node<'a>,
   el1 : Node<'a>,
   el2 : Node<'a>,
   el3 : Node<'a>,
   el4 : Node<'a>,
   el5 : Node<'a>,
   el6 : Node<'a>,
   sentinel : Node<'a>,
   list : List<'a>,
}
  fn remove_cur<'a>(mut iter : &mut Option<&mut Node<'a> >) -> &'a mut Node<'a> {
      match *iter {
        Some(ref mut glob_next) => {
             let rest : Option<&'a mut Node <'a> >;
             match glob_next.next {
                 Some(ref mut root_cell) => {
                    rest = std::mem::replace(&mut root_cell.next, None);
                 },
                 None => rest = None,
             }
             match std::mem::replace(&mut glob_next.next, rest) {
                Some(mut root_cell) =>
                {
                   return root_cell;
                },
                None => panic!("Empty list"),
             }
        },
        None => panic!("List not initialized"),
     }
  }

impl<'a> List<'a> {
  fn remove_first(self : &mut List<'a>) -> &'a mut Node<'a> {
      return remove_cur(&mut self.glob);
  }

  fn remove_search(self : &mut List<'a>, searched:i32) -> &'a mut Node<'a> {
      let mut list_iter : &mut Option<&'a mut Node<'a> > = &mut self.glob;
      loop {
          match *list_iter {
              Some(ref mut cur_cell) => {
                match cur_cell.next {
                   Some(ref item) => {
                       if cur_cell.val == searched {
                            break;
                       }
                   },
                   None=>{},
                  }
                  list_iter = &mut cur_cell.next;
              },
              None => { // use whatever is available if nothing matches well
                  panic!("Not found");
              },
         }
    }
    return remove_cur(list_iter);
 }
}

fn main() {
    let mut a : AllocatedList = AllocatedList{
        el0 : Node{val : 0, next : None},
        el1 : Node{val : 1, next : None},
        el2 : Node{val : 2, next : None},
        el3 : Node{val : 3, next : None},
        el4 : Node{val : 4, next : None},
        el5 : Node{val : 5, next : None},
        el6 : Node{val : 6, next : None},
        sentinel : Node {val : -1, next : None},
        list : List{glob:None},
    };
    a.el5.next = Some(&mut a.el6);
    a.el4.next = Some(&mut a.el5);
    a.el3.next = Some(&mut a.el4);
    a.el2.next = Some(&mut a.el3);
    a.el1.next = Some(&mut a.el2);
    a.el0.next = Some(&mut a.el1);
    a.sentinel.next = Some(&mut a.el0);
    a.list.glob = Some(&mut a.sentinel);
    let removed_el = a.list.remove_first();
    println!("Removed {:?}", removed_el.val);
    let removed_el = a.list.remove_first();
    println!("Removed {:?}", removed_el.val);

    let removed_x = a.list.remove_search(5);
    println!("Removed {:?}", removed_x.val);
}

错误是：

52:36 error: cannot borrow `list_iter.0` as mutable more than once at a time [E0499]
          Some(ref mut cur_cell) => {
               ^~~~~~~~~~~~~~~~
69:3 note: previous borrow ends here
     fn remove_search(self : &mut List<'a>, searched:i32) -> &'a mut Node<'a> {

61:49 error: cannot assign to `list_iter` because it is borrowed [E0506]
              list_iter = &mut cur_cell.next;
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
52:36 note: borrow of `list_iter` occurs here
             Some(ref mut cur_cell) => {
                  ^~~~~~~~~~~~~~~~

是否有任何我可以遵循的方法或我可以在我的代码中进行的任何更改（需要使用 nostdlib）来遍历此列表？

我不想使用递归，因为它在实践中可能会变得相当大，而且我不希望溢出堆栈。

Answer 1

我得到了一个递归版本（粘贴在这里以供其他人参考）但有人可以帮我将它转换为迭代版本：如果可能的话，我宁愿不受堆栈大小的限制。

// This code is placed in the public domain
struct Node<'a> {
    val : i32,
    next : Option<&'a mut Node<'a> >,
}
struct List<'a> {
    glob : Option<&'a mut Node<'a> >,
}


struct AllocatedList<'a> {
   el0 : Node<'a>,
   el1 : Node<'a>,
   el2 : Node<'a>,
   el3 : Node<'a>,
   el4 : Node<'a>,
   el5 : Node<'a>,
   el6 : Node<'a>,
   el7 : Node<'a>,
   sentinel : Node<'a>,
   list : List<'a>,
}
  fn remove_cur<'a>(mut iter : &mut Option<&mut Node<'a> >) -> &'a mut Node<'a> {
      match *iter {
        Some(ref mut glob_next) => {
             let rest : Option<&'a mut Node <'a> >;
             match glob_next.next {
                 Some(ref mut root_cell) => {
                    rest = std::mem::replace(&mut root_cell.next, None);
                 },
                 None => rest = None,
             }
             match std::mem::replace(&mut glob_next.next, rest) {
                Some(mut root_cell) =>
                {
                   return root_cell;
                },
                None => panic!("Empty list"),
             }
        },
        None => panic!("List not initialized"),
     }
  }

  fn remove_search_recursive<'a> (mut node : &mut Option<&mut Node <'a> >, searched:i32) -> &'a mut Node<'a> {
    let mut found : bool = false;
    {
        match *node {
            Some(ref mut cur_cell) => {
                match cur_cell.next {
                    Some(ref item) => {
                        if item.val == searched {
                               found = true;
                        }
                    },
                    None => panic!("Not found"),
                 }
                 if !found {
                    return remove_search_recursive(&mut cur_cell.next, searched);
                 }
            },
            None => panic!("Not impl"),
        }
    }
    if found {
       return remove_cur(node);
    }
    panic!("Not impl");
 }

impl<'a> List<'a> {
  fn remove_first(self : &mut List<'a>) -> &'a mut Node<'a> {
      return remove_cur(&mut self.glob);
  }
  fn remove_search_recursive(self : &mut List<'a>, searched:i32) -> &'a mut Node<'a> {
     return remove_search_recursive(&mut self.glob, searched);
  }
}
fn main() {
    let mut a : AllocatedList = AllocatedList{
        el0 : Node{val : 0, next : None},
        el1 : Node{val : 1, next : None},
        el2 : Node{val : 2, next : None},
        el3 : Node{val : 3, next : None},
        el4 : Node{val : 4, next : None},
        el5 : Node{val : 5, next : None},
        el6 : Node{val : 6, next : None},
        el7 : Node{val : 7, next : None},
        sentinel : Node {val : -1, next : None},
        list : List{glob:None},
    };
    a.el6.next = Some(&mut a.el7);
    a.el5.next = Some(&mut a.el6);
    a.el4.next = Some(&mut a.el5);
    a.el3.next = Some(&mut a.el4);
    a.el2.next = Some(&mut a.el3);
    a.el1.next = Some(&mut a.el2);
    a.el0.next = Some(&mut a.el1);
    a.sentinel.next = Some(&mut a.el0);
    a.list.glob = Some(&mut a.sentinel);
    let removed_el = a.list.remove_first();
    println!("Removed {:?}", removed_el.val);
    let removed_el = a.list.remove_first();
    println!("Removed {:?}", removed_el.val);

    let removed_x = a.list.remove_search_recursive(5);
    println!("Removed {:?}", removed_x.val);
    let removed_y = a.list.remove_search_recursive(3);
    println!("Removed {:?}", removed_y.val);
}

不使用标准库时如何迭代搜索并从列表中删除

How to iteratively search and remove from a list when not using the standard library

lifetime

rust

borrow-checker