STLを使用してLFUキャッシュを実装する方法は？

Question

私は純粋なSTLを使ってLFU（Least Frequently Used）キャッシュを実装しようとしています（私はBoostを使いたくありません！）。

要件は以下のとおりです。std::mapと同じようKeyを使って任意の要素に

• 連想アクセス。
• 最低優先度のアイテムを解放する機能（UsesCount属性を使用）。
• アイテムの優先度（UsesCount）を更新する機能。問題がある

：

• Iアイテム（Key、Value、UsesCount）のコンテナとしてstd::vectorを使用する場合、連想アクセスとstd::make_heap用ベクターへのイテレータの容器としてstd::map、std::push_heapとstd::pop_heapベクトル内での優先度キューの実装として、マップ内のイテレータはヒープ操作後に有効ではありません。
• 前のコンフィグレーションでstd::vectorの代わりにstd::list（またはstd::map）を使用すると、イテレータがaritmeticをサポートしないため、std::make_heapなどをコンパイルできません。
• std::priority_queueを使用したい場合、アイテムの優先度を更新する機能はありません。

質問は以下のとおりです。

• 私はこの問題を解決する方法を明らかに何かが足りないのですか？
• 以前の要件を満たすLFUキャッシュの純粋なC++/STL実装を例として挙げてください。

あなたの洞察をいただきありがとうございます。

Answer 1

*_heap関数を使用してmakeを実装すると、ベクターがうまくフィットしているようです。更新が遅くなることもあります。発生するイテレータの無効化に関する問題は、基本的なデータ構造としてベクトルを使用するすべてのコンテナで通常です。これはまたboost::heap::priority_queueによって取られたアプローチですが、上記の理由で可変インターフェースを提供しません。 boost::heap data-structuresは、ヒープを更新する機能を提供します。

少し奇妙なもの：std::priority_queueを使用することができますが、イテレータの無効化の問題に直面します。

あなたの質問に直接答えるには：あなたは何かが明らかに欠けているわけではありません。 std::priority_queueはそれほど有用ではありません。最良の方法は、更新をサポートする独自のヒープ実装を作成することです。完全にSTL互換（特にアロケータ対応）にするのはやや難しく、単純な作業ではありません。さらに、LFUキャッシュを実装します。

最初のステップは、Boostの実装を見て、その努力のアイデアを得ることです。私は2番目のリファレンス実装について認識していません。それは追加コストを作成し、非常に厄介な得ることができるよう、あなたがそれを回避しようとすべきであるが、あなたは常に、別の容器に間接を選択することができますイテレータの無効化を回避するために

。

Answer 2

A 2つのデータ構造を維持するよりも、やや単純なアプローチ：

• ちょうど彼らの価値/使用カウントペアにあなたのキーをマッピングマップをキープ。
• キャッシュがいっぱいです：
• • は
  （O(n)）最悪の10％を見つけるためにstd::nth_elementを使用

• （O(n)）地図要素にイテレータのベクトルを作成します
• • マップからそれらのすべてを削除する（O(n log n)）

ので、キャッシュに新しい要素を追加する一般的なケースO(log n)、最悪の場合O(n log n)で、O(log n)を償却。新しいエントリがトップの90％を作るために持っているか、それらはカットしているので、最悪の10％を削除

は、LFUキャッシュにビット抜本的なかもしれません。また、1つの要素だけを削除しても、新しいエントリは、次の新しいエントリの前に一番下から降りる必要があります。だからなぜLFUがあなたにとって正しいキャッシング戦略なのかによって、私の変更は間違った戦略かもしれないし、それでも問題ないかもしれません。