基本

• 所有権規則
  • Rustの各値は、所有者と呼ばれる変数と対応している。
  • いかなる時も所有者は一つである。
  • 所有者がスコープから外れたら、値は破棄される。
    • i64 のような Copy 可能な型でもそう
• 参照
  • 値に対する参照は、1個の可変参照または1個以上の不変参照のどちらか一方のみ取れる
    • つまり、参照を持った変数は自分の預かり知らぬところで値が変化することはない。
  • ダングリング参照（値はスコープから外れて破棄されているのに、参照は生きている）は持てないようにコンパイラが保証している
    • 参照がスコープから抜けるまで、データがスコープから抜けることはないようになっている

マージテク

マージテクを素朴に実装すると、不変参照と可変参照を両方取ることになりエラーになる。

std::mem::take を使うことで回避する。

マージテク を参照

取得も &mut な構造体

例えば UnionFind は取得するときも &mut self になっている。

Union Find で filter, map を書くとエラーになりがち。

// こう書くとエラーになる (cannot borrow `uf` as mutable more than once at a time)
let sum = (0..nv)
    .filter(|&v| uf.root(v) == v)
    .map(|v| {
        let cnt = uf.same_count(v);
        nc2(cnt)
    })
    .sum::<usize>();

filter にわたすクロージャーと map にわたすクロージャーの両方に uf の可変参照を渡してしまっているので、エラーになる。

可変参照で filter, map を使いたい場合は、かわりに filter_map を使うと良い（クロージャーが一つになるので、複数参照を作らなくて済む）

// filter_map を使うとよい。
let sum = (0..nv)
    .filter_map(|v| {
        if uf.root(v) == v {
            let cnt = uf.same_count(v);
            Some(nc2(cnt))
        } else {
            None
        }
    })
    .sum::<usize>();

// 単純に for ループでもよい
let mut sum = 0;
for v in 0..nv {
    if uf.root(v) == v {
        let cnt = uf.same_count(v);
        sum += nc2(cnt);
    }
}

一部の構造体は取得系も &mut になっていることがある。以下は例

• Union Find（経路圧縮）
• 遅延セグ木（遅延していた分の計算）

二重クロージャー