5

std::set コンテナについて簡単な質問があります。現在、プッシュバック機能を使用してセットにフィードしています。もちろん、セットは push_back ごとにどんどん大きくなります。最新の 30 要素程度にのみ関心があります。古い要素は削除できます。したがって、私の考えは、セットのサイズを 30 要素程度に制限し、そうすることで不要な古い要素を取り除くことです。ただし、このセットはデフォルトでは制限をサポートしていません。セットのサイズを時々チェックして、余分な要素を手動で削除することができました。よりスマートな方法はありますか？

よろしくルンピ

4

4 に答える 4

6

解決策として、データ構造をクラスにカプセル化しset、そのクラスで要素数を制御できます。

于 2011-01-30T13:18:20.947 に答える
3

LRU 構造を自分で構築する必要があります。これを行う 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 リストを使用して最も古いエントリをすばやく見つけることができます。

この以前のスタックオーバーフローの質問で、LRU リストを作成する方法に関するその他の提案を見つけることができます。

于 2011-01-30T13:17:49.423 に答える
1

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

于 2011-01-30T13:18:21.983 に答える
0

時間があったので、セットとリストでやってみました。リストは、最後に挿入された n 個の要素を追跡するだけです。また、一般的な消去を実装しました。パフォーマンスを向上させるには (set が順序付けられているという事実を利用していない場合)、unordered_set の使用を検討してください。include <set>（とinclude <unordered_set>同様にstd::set置き換えますstd::unordered_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;
}

結果：

should see 2 3
elements: 2
elements: 3
should see 4
elements: 4
于 2016-03-02T12:05:53.100 に答える