2026-09-05
ttl_cache.rs
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
struct Cache {
map: HashMap<&'static str, (i32, u64)>,
expiry: BinaryHeap<Reverse<(u64, &'static str)>>,
}
impl Cache {
fn put(&mut self, key: &'static str, value: i32, expires: u64) {
self.map.insert(key, (value, expires));
self.expiry.push(Reverse((expires, key)));
}
fn purge(&mut self, now: u64) {
while self.expiry.peek().is_some_and(|Reverse((e, _))| *e <= now) {
let Reverse((_, key)) = self.expiry.pop().unwrap();
self.map.remove(key);
}
}
}
有効期限つきのキャッシュ Cache です。put は値と期限を入れ、purge(now) は期限が now 以下の値を消します。期限の早い順に取り出せるよう、期限とキーの組を BinaryHeap にも積んでいます。空の Cache に put("a", 1, 10)、put("b", 2, 12)、put("a", 3, 20) の順に入れて purge(11) を呼び、"a" と "b" の値を {:?} で出すと、いまは None Some(2) です。本来は Some(3) Some(2) です。
Answer
Wrong
let Reverse((_, key)) = self.expiry.pop().unwrap();
self.map.remove(key);
BinaryHeap は大きい値から取り出すヒープですが、Reverse で包んでいるので、期限の小さい組から順に出てきます。purge(11) が最初に取り出すのは (10, "a") で、期限 10 は 11 以下なので、map.remove("a") を呼びます。次の (12, "b") は 11 より後なので、そこで止まります。ここまでは <= の境界も Reverse の向きも正しく働いています。
食い違いは put("a", 3, 20) で生まれています。map.insert は "a" の値を (3, 20) に上書きしますが、ヒープには古い (10, "a") を残したまま (20, "a") を足します。purge はこの古い組をキーだけで信じて消すので、実際に消えるのは期限を 20 に延ばした新しい値 3 です。BinaryHeap から先頭以外の組を消すには retain でヒープ全体をなめ直すしかなく、put のたびにそうするとヒープで期限を管理する意味が薄れます。
Right
let Reverse((expires, key)) = self.expiry.pop().unwrap();
if self.map.get(key).is_some_and(|&(_, e)| e == expires) {
self.map.remove(key);
}
ヒープから出した組の期限が、map にある今の期限と同じときだけ消します。(10, "a") は map の期限 20 と一致しないので読み捨てられ、"a" は残ります。(20, "a") は、時刻 20 以降の purge で取り出されたときに一致して、そこで消えます。ヒープの組は期限を書き換えるたびに古くなりうる控えなので、消す前に map と照らし合わせる必要があります1。
- 消せない要素をヒープに残しておき、取り出したときに古ければ捨てるやり方は、遅延削除(lazy deletion)と呼ばれます。ダイクストラ法で同じ頂点を何度も
BinaryHeapに積み、取り出した距離が古ければ飛ばす書き方も同じ形です。