重複の可能性：
LRUキャッシュ設計
私はプログラミングのインタビューでこの質問を受けました。どのように答えるかを自由に考えてください。
C ++でLRU（最近更新されていない）キャッシュをどのように実装しますか？基本的に、キャッシュは最大Nアイテムを保持できます。新しいアイテムが挿入され、キャッシュ内のアイテムの数が、未満の場合、そのアイテムは挿入されたNだけです。ただし、新しいアイテムが挿入され、キャッシュ内のアイテムの数がすでにある場合はN、使用頻度が最も低いアイテムをキャッシュから削除する必要があります。
各操作にかかる実行時間を考えてください。
最終アクセス時間を格納するキャッシュ要素のメンバーがあります。要素がアクセスされると（メンバー関数が呼び出される）、アクセス時間メンバーが更新されます。キャッシュがいっぱいになると、アクセス時間が最小の要素が消去されます。
他のオプションは、侵入リストにキャッシュ要素を含めることです。何かがアクセスされ、リストの一番上にない場合、それはリストの一番上になります。キャッシュがいっぱいになると、リストの一番下の要素が消去されます。各アクセスでより多くの作業が行われますが、被害者をすばやく見つけることができます。
基本的な考え方は、そのようなタスクのための典型的なマップとリストを持たないことです。これらはあなたの記憶を断片化します。私のアルゴリズムは、キャッシュを常に1か所に保持します。