LRUキャッシュで一般的に使用され、オブジェクトをすばやく見つけるために使用されるデータ構造は何ですか？

Question

私は、アプリケーションにとって重要なオブジェクトをすばやく見つけるためにHashTableを実装しようとしました。

しかし、どのオブジェクトに最後にアクセスしたのかを特定するために、スキャンする考え方と、テーブル全体をロックする必要があるという考えが嫌いです。テーブルがかなり大きくなる可能性があります。

これを克服するために一般的に使用されるデータ構造は何ですか？

私は何かが何かを知るために、オブジェクトをFIFOとキャッシュに投げ込めると思った。しかし、それはLRUアルゴリズムをサポートするつもりはありません。

アイデア？イカはどうしているの？

Answer 1

リンクリストは、LRUキャッシュに適しています。リンクリスト内の索引付き検索（リンクされたリストの最後に使用された最後にエントリを移動する）の場合は、ハッシュテーブルを使用します。最も最近に使用されたエントリは常にリンクリストの最後になります。

Answer 2

このarticleは、STLコンテナ（またはboost::bimapベースの代替）を使用してLRUキャッシュの実装に役立つことがあります。 STLでは、基本的にマップ（高速キー値検索用）とそのキーまたはイテレータの個別リスト（アクセス履歴の簡単な保守用）を組み合わせて使用​​します。