limitar o tamanho de um std :: set

Question

Tenho uma pequena pergunta sobre o contêiner std :: set.No momento, estou alimentando meu conjunto usando a função pushback.É claro que o conjunto se torna cada vez maior a cada push_back. Estou interessado apenas nos últimos 30 elementos ou mais ... Os elementos mais antigos podem ser excluídos.Portanto, minha ideia é limitar o tamanho do conjunto a cerca de 30 elementos e, ao fazer isso, livrar-se dos elementos antigos indesejados.No entanto, o conjunto não suporta um limite por padrão.Eu poderia verificar o tamanho do conjunto de vez em quando e excluir manualmente os elementos excedentes. Existe uma maneira mais inteligente?

Atenciosamente, Lumpi

Answer 1

Você mesmo precisará construir uma estrutura LRU.Uma maneira de fazer isso seria ter std :: map e std :: list apontando para os iteradores um do outro.Isto é:

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;

Sempre que você procurar uma entrada no mapa, mova a entrada da lista associada para o início da lista.Ao adicionar uma entrada ao mapa, crie um novo lru_entry, adicione-o ao mapa e à lista e atualize os iteradores na estrutura lru_entry.Quando o mapa de pesquisa exceder 30 entradas, você poderá usar a lista lru para encontrar rapidamente a entrada mais antiga.

Você pode encontrar mais sugestões sobre como criar uma lista de LRU em esta questão stackoverflow anterior.

Answer 2

Como solução, você pode encapsular a estrutura de dados set em uma classe e, nessa classe, controlar a contagem dos elementos.

Answer 3

O conjunto não apenas não suporta um limite, mas também não informa a idade do elemento.Crie uma nova classe que encapsula um contêiner.Essa classe pode então fornecer métodos para impor o limite de tamanho ao adicionar elementos ou explicitamente.Uma fila seria ideal se a remoção fosse feita com base em quando o elemento foi adicionado (é otimizado para operações em ambas as extremidades).

Answer 4

Como eu tinha tempo, faria isso usando um conjunto e uma lista.A lista apenas mantém o controle dos últimos n elementos inseridos.Também implementou um apagamento geral.Para um melhor desempenho (se você não está aproveitando o fato de que o conjunto está ordenado), você pode considerar o uso de unordered_set.(substitua include <set> por include <unordered_set>, bem como std::set por 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