Begrenzen Sie die Größe eines std :: set

Question

Ich habe eine kurze Frage zum std :: set-Container.Im Moment füttere ich mein Set mit der Pushback-Funktion.Natürlich wird die Menge mit jedem Push_back größer und größer. Ich interessiere mich nur für die letzten 30 Elemente oder so ... Die älteren Elemente können gelöscht werden.Meine Idee ist es also, die Größe des Sets auf ungefähr 30 Elemente zu beschränken und auf diese Weise die unerwünschten älteren Elemente zu entfernen.Das Set unterstützt jedoch standardmäßig kein Limit.Ich könnte ab und zu die Größe des Sets überprüfen und die überschüssigen Elemente manuell löschen. Gibt es einen intelligenteren Weg?

Grüße Lumpi

Answer 1

Sie müssen selbst eine LRU-Struktur erstellen.Eine Möglichkeit, dies zu tun, wäre, eine std :: map und eine std :: list zu haben, die auf die Iteratoren des jeweils anderen verweisen.Das heißt:

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;

Wenn Sie einen Eintrag in der Karte nachschlagen, verschieben Sie den zugehörigen Listeneintrag an den Anfang der Liste.Wenn Sie der Karte einen Eintrag hinzufügen, erstellen Sie einen neuen lru_entry, fügen Sie ihn sowohl der Karte als auch der Liste hinzu und aktualisieren Sie die Iteratoren in der lru_entry-Struktur.Wenn die Suchkarte 30 Einträge überschreitet, können Sie mithilfe der lru-Liste schnell den ältesten Eintrag finden.

Weitere Vorschläge zum Erstellen einer LRU-Liste finden Sie in dieser vorherigen Stackoverflow-Frage.

Answer 2

Als Lösung können Sie die set-Datenstruktur in eine Klasse kapseln und in dieser Klasse die Anzahl der Elemente steuern.

Answer 3

Die Menge unterstützt nicht nur kein Limit, sondern gibt auch nicht das Alter des Elements an.Erstellen Sie eine neue Klasse, die einen Container kapselt.Diese Klasse kann dann Methoden bereitstellen, um die Größenbeschränkung beim Hinzufügen von Elementen oder explizit zu erzwingen.Eine Warteschlange ist ideal, wenn das Entfernen basierend auf dem Zeitpunkt des Hinzufügens des Elements erfolgt (es ist für Operationen an beiden Enden optimiert).

Answer 4

Da ich Zeit hatte, würde ich es mit einem Set und einer Liste tun.Die Liste verfolgt nur die letzten n eingefügten Elemente.Auch ein allgemeines Löschen implementiert.Für eine bessere Leistung (wenn Sie die Tatsache, dass das Set bestellt ist, nicht ausnutzen) können Sie die Verwendung von unordered_set in Betracht ziehen.(Ersetzen Sie den include <set> durch den include <unordered_set> sowie den std::set durch den 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;
}

Ergebnis:

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