26

特定の位置に要素を挿入するために、再帰的なデータ構造を繰り返しナビゲートしようとしています。私の限られた理解では、これは、構造のルートへの変更可能な参照を取得し、それをそのフォロワーへの参照で連続的に置き換えることを意味します。

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(ref mut node) = *anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

(さび遊び場リンク)

ただし、これは失敗します。

error[E0499]: cannot borrow `anchor.0` as mutable more than once at a time
  --> src/main.rs:14:24
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ^^^^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
18 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `anchor` because it is borrowed
  --> src/main.rs:15:13
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ borrow of `anchor` occurs here
15 |             anchor = &mut node.next;
   |             ^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `anchor` occurs here

error[E0499]: cannot borrow `*anchor` as mutable more than once at a time
  --> src/main.rs:17:9
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ first mutable borrow occurs here
...
17 |         anchor
   |         ^^^^^^ second mutable borrow occurs here
18 |     }
   |     - first borrow ends here

これは両方とも同じ構造anchorを参照しているため意味がありますが、実際には構造を破壊した後nodeは気にしません。anchor

back()安全なRustを使用して正しく実装するにはどうすればよいですか?

4

4 に答える 4

25

それは可能です...しかし、もっとエレガントな解決策があればいいのにと思います。

秘訣は、 から借用しないことanchorです。したがって、2 つのアキュムレータの間でジャグリングします。

  • 現在のノードへの参照を保持するもの
  • もう一方には次のノードへの参照が割り当てられます

これにより、次のことがわかります。

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            let tmp = anchor;
            if let Some(ref mut node) = *tmp {
                anchor = &mut node.next;
            } else {
                anchor = tmp;
                break;
            }
        }

        anchor
    }
}

正確にはきれいではありませんが、これは借用チェッカーが遅れることがあるため、¯\_(ツ)_/¯ です。

@ker は、名前のない一時的なものを作成することでこれを改善しました:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            match {anchor} {
                &mut Some(ref mut node) => anchor = &mut node.next,
                other => return other,
            }
        }
    }
}

ここでの秘訣は、 using{anchor} がの内容anchorを、一致が実行される名前のない一時ファイルに移動することです。したがって、match借用しているブロックではanchor、一時的なものからではなく、自由に変更できanchorます。関連するブログ投稿Stuff the Identity Function Does (in Rust)を参照してください。

于 2016-06-23T09:12:48.810 に答える
7

再帰を使用して借用チェッカーを満たすことができます。これには、リスト内のすべてのアイテムに対してスタック フレームが作成されるという欠点があります。リストが長い場合、これは確実にスタック オーバーフローに陥ります。LLVM はメソッドをループに最適化します (プレイグラウンドNode::backで生成された LLVM IR を参照してください)

impl Node {
    fn back(&mut self) -> &mut Link {
        match self.next {
            Some(ref mut node) => node.back(),
            None => &mut self.next,
        }
    }
}

impl Recursive {
    fn back(&mut self) -> Option<&mut Link> {
        self.root.as_mut().map(|node| node.back())
    }
}
于 2016-06-23T09:10:59.333 に答える
2

できます：

fn back(&mut self) -> &mut Link {
    let mut anchor = &mut self.root;
    while anchor.is_some(){
        anchor = &mut {anchor}.as_mut().unwrap().next;
    }
    anchor
}
于 2016-06-23T09:47:29.440 に答える