Namaran

Code daily. Without assist.

2026-09-06

interner.rs

use std::collections::HashMap;

fn intern(ids: &mut HashMap<String, usize>, names: &mut Vec<String>, name: &str) -> usize {
    *ids.entry(name.to_string()).or_insert({
        names.push(name.to_string());
        names.len() - 1
    })
}

fn main() {
    let mut ids = HashMap::new();
    let mut names = Vec::new();
    let got = ["a", "b", "a", "c"].map(|n| intern(&mut ids, &mut names, n));
    println!("{got:?} {names:?}");
}

文字列に 0 から順に ID を振る intern です。同じ文字列には同じ ID を返し、names[id] でその文字列を引けるようにするつもりです。"a"、"b"、"a"、"c" を順に intern すると、いまは [0, 1, 0, 3] ["a", "b", "a", "c"] と出力されます。本来の出力は [0, 1, 0, 2] ["a", "b", "c"] です。どこを直せばよいでしょうか?

Answer

or_insert({ ... }) を or_insert_with(|| { ... }) に変えます。

出力を見ると、2回目の "a" には正しく 0 が返っているのに、names には "a" がもう1つ積まれています。既にある文字列でも push が実行されたということで、その分 names.len() が1つ進み、次の "c" が 3 になりました。

or_insert はエントリが空いているときだけ値を入れるメソッドですが、渡している { ... } はブロック式です。あとで必要になったときに実行されるコードではなく、評価するとその場で値になる式なので、関数の引数としては呼び出しの前に評価されます。ブロックの中の push は、エントリが空いているかどうかに関係なく、or_insert が呼ばれる前に毎回実行されます。2回目の "a" では、ブロックが返した 2 は捨てられ、push の効果だけが残ります。

or_insert_with はクロージャを受け取り、エントリが空いているときだけそれを呼びます。push と len がクロージャの中に移るので、新しい文字列のときにしか動きません。元のブロックと同じく、クロージャが借用する names は entry が借用している ids とは別の変数なので、借用の衝突も起きません。