マージテク

マージテク を参照

Union Find のような取得も &mut な構造体

// こう書くとエラーになる (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>();

// こう書けばOK
let mut sum = 0;
for v in 0..nv {
    if uf.root(v) == v {
        let cnt = uf.same_count(v);
        sum += nc2(cnt);
    }
}

// filter_map を使うのでもOK
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>();

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

可変なものを扱う場合は filter, map を使うより、おとなしく for ループを書くほうがよさそう。filter_map を使うのもあり。

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

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

Iterator を作るクロージャー

// これだとエラーになる (lifetime may not live long enough)
|p: &Pos<i64>| DIR4_LIST.iter().map(move |d| *d + *p);

// ↓こうしたらコンパイル通った
|p: Pos<i64>| DIR4_LIST.iter().map(move |d| *d + p);