Limite el tamaño de un std :: set

Question

Tengo una breve pregunta sobre el contenedor std :: set. En este momento estoy alimentando mi conjunto usando la función de retroceso. De Corse, el conjunto se vuelve cada vez más grande para cada push_back. Solo estoy interesado en los últimos 30 elementos más o menos ... Los elementos más antiguos se pueden eliminar. Entonces, mi idea es limitar el tamaño del conjunto a 30 elementos más o menos y al deshacerse de los elementos mayores no deseados. Sin embargo, el conjunto no admite un límite por defecto. Podría verificar el tamaño del set de vez en cuando y eliminar manualmente los elementos excesivos. ¿Hay una manera más inteligente?

Saludos lumpi

Answer 1

Tendrá que construir una estructura LRU usted mismo. Una forma de hacer esto sería tener un std :: map y std :: list apuntando a los iteradores del otro. Eso es:

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;

Siempre que busque una entrada en el mapa, mueva su entrada de lista asociada al inicio de la lista. Al agregar una entrada al mapa, cree un nuevo LRU_ENTRY, agréguela tanto al mapa como a la lista, y actualice los iteradores en la estructura LRU_Entry. Cuando el mapa de búsqueda excede las 30 entradas, puede usar la lista LRU para encontrar rápidamente la entrada más antigua.

Puede encontrar más sugerencias sobre cómo construir una lista de LRU en Esta pregunta anterior de Stackoverflow.

Answer 2

Como solución puede encapsular el set Estructura de datos en una clase y en esa clase Control los elementos cuentan.

Answer 3

El conjunto no solo no admite un límite, sino que tampoco le dice la edad del elemento. Cree una nueva clase que encapsule un contenedor. Esa clase puede proporcionar métodos para hacer cumplir el límite de tamaño al agregar elementos o explícitamente. Una cola sería ideal si la eliminación se realiza en función de cuándo se agregó el elemento (está optimizado para operaciones en ambos extremos).

Answer 4

Como tenía tiempo, lo haría usando un conjunto y una lista. La lista solo hace un seguimiento de los últimos n elementos insertados. También implementó un borrado general. Para un mejor rendimiento (si no está aprovechando el hecho de que se ordena el conjunto), puede considerar usar undered_set. (reemplazar include <set> con include <unordered_set> tanto como std::set con 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;
}

resultado:

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