std :: setのサイズを制限する

Question

私はstd :: setコンテナに関する簡単な質問があります。今私はプッシュバック機能を使用して私のセットを供給しています。コースのうち、セットはpush_backごとに大きくなります。 私は最新の30要素程度のものしか知りません...古い要素は削除できます。だから、私の考えは、30要素程度にセットのサイズを制限し、不要な古い要素を取り除くことです。ただし、このセットはデフォルトでは制限をサポートしていません。私はしばらくの間、セットのサイズを確認して余分な要素を手作業で削除することができました。 スマートな方法がありますか？あなたはLRU構造を自分で構築する必要があります

よろしくLumpi

Answer 1

。これを行う1つの方法は、std :: mapとstd :: listを互いのイテレータを指すようにすることです。つまり、

struct lru_entry { 
    std::list<lru_entry *>::iterator lru_iterator; 
    std::map<your_data, lru_entry *>::iterator map_iterator; 
}; 

std::list<lru_entry *> lru; 
std::map<your_data, lru_entry *> lookup; 

マップのエントリをルックアップするときは、関連するリストエントリをリストの先頭に移動します。エントリをマップに追加するときは、新しいlru_entryを作成し、マップとリストの両方に追加し、lru_entry構造体のイテレータを更新します。ルックアップマップが30エントリを超えると、lruリストを使用して最も古いエントリをすばやく見つけることができます。

あなたがクラスにと要素がカウントそのクラスの制御にsetデータ構造をカプセル化することができます解決策としてthis previous stackoverflow question.

Answer 2

にLRUリストを作成する方法の詳細提案を見つけることができます。

Answer 3

このセットは、制限をサポートしているだけでなく、要素の有効期間も教えてくれません。コンテナをカプセル化する新しいクラスを作成します。そのクラスは、要素を追加するときや明示的にサイズ制限を適用するメソッドを提供します。要素が追加されたとき（両端での操作に最適化されている）に基づいて削除が行われる場合、キューが理想的です。

Answer 4

私は時間があったので、セットとリストを使ってやりました。リストは、最後に挿入されたn個の要素を追跡します。また、一般的な消去を実装しました。パフォーマンスを向上させるには（setが注文されていることを利用していない場合）、unordered_setの使用を検討することができます。 （include <unordered_set>ならびにstd::unordered_setとstd::setとinclude <set>を置き換える）

#include <set> 
#include <list> 
#include <assert.h> 

template<typename T> 
struct setkeepn { 
    std::set<T> mSet; 
    std::list<T> mLast; 
    void insert(T element) { 
     if (mSet.find(element) == mSet.end()) { 
      assert(mSet.size() == mLast.size()); 
      // put your limit of 30 below 
      if (mSet.size() >= 2) { 
       T extra = mLast.back(); 
       mSet.erase(extra); 
       mLast.pop_back(); 
      } 
      mSet.insert(element); 
      mLast.push_front(element); 
     } 
    } 
    void erase(T element) 
    { 
     typename std::set<T>::iterator lToEraseFromSet = mSet.find(element); 
     if (lToEraseFromSet != mSet.end()) { 
      // linear on the number of elements. 
      typename std::list<T>::iterator lToEraseFromList = std::find(mLast.begin(),mLast.end(), element); 
      assert(lToEraseFromList != mLast.end()); 

      mSet.erase(lToEraseFromSet); 
      mLast.erase(lToEraseFromList); 
     } 
    } 
}; 

int main(int argc, const char * argv[]) { 

    setkeepn<int> lTest; 
    lTest.insert(1); 
    lTest.insert(2); 
    lTest.insert(2); 
    lTest.insert(3); 
    printf("should see 2 3\n"); 
    for (auto e : lTest.mSet) { // 2,3 
     printf("elements: %d\n",e); 
    } 
    lTest.insert(4); 

    lTest.erase(3); 
    printf("should see 4\n"); 
    for (auto e : lTest.mSet) { // 4 
     printf("elements: %d\n",e); 
    } 

    return 0; 
} 

結果：[製品コードでLRU実装]の

should see 2 3 
elements: 2 
elements: 3 
should see 4 
elements: 4