[解決済み] LRUキャッシュの設計

質問

LRU（Least Recently Used）キャッシュとは、最近使ったものから順に破棄していくキャッシュのことです。 このようなキャッシュクラスをどのように設計し、実装するのでしょうか？設計要件は次のとおりです。

1) できるだけ速くアイテムを見つける

2) キャッシュがミスして満杯になったら、できるだけ早く最近使ったアイテムを置き換える必要がある。

この問題をデザインパターンやアルゴリズム設計の観点からどのように分析し、実装すればよいでしょうか？

どのように解決するのですか？

リンクリスト＋リンクリストのノードへのポインタのハッシュテーブルが、LRUキャッシュを実装する通常の方法である。これは O(1) 操作を与えます (適切なハッシュを仮定しています)。この（O(1)である）利点は、構造体全体をロックすることでマルチスレッド化することができることです。粒状ロックなどについて心配する必要はありません。

簡単に言うと、動作方法です。

値のアクセス時に、リンクリストの対応するノードを先頭に移動させる。

キャッシュから値を削除する必要があるときは、末尾から削除します。

キャッシュに値を追加するときは、リンクリストの先頭に置くだけです。

doublepさんのおかげで、C++で実装されたサイトがあります。 その他のコンテナ・テンプレート .