ограничить размер std :: set

Question

У меня короткий вопрос о контейнере std :: set.Прямо сейчас я кормлю свой набор, используя функцию pushback.Конечно, набор становится больше и больше для каждого push_back.Меня интересуют только последние 30 элементов или около того ... Старые элементы могут быть удалены.Поэтому моя идея состоит в том, чтобы ограничить размер набора до 30 элементов или около того и таким образом избавиться от нежелательных старых элементов.Однако набор не поддерживает ограничение по умолчанию.Я мог бы проверять размер набора время от времени и вручную удалять лишние элементы.Есть ли более умный способ?

С уважением, Lumpi

Answer 1

В качестве решения вы можете инкапсулировать структуру данных set в класс и в этом классе управлять количеством элементов.

Answer 2

Вам нужно будет самостоятельно построить структуру LRU. Одним из способов сделать это было бы иметь 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 в этом предыдущем вопросе stackoverflow.

Answer 3

Набор не только не поддерживает ограничение, но и не сообщает вам возраст элемента.Создайте новый класс, который инкапсулирует контейнер.Затем этот класс может предоставлять методы для принудительного ограничения размера при добавлении элементов или явно.Очередь была бы идеальной, если удаление выполняется в зависимости от того, когда был добавлен элемент (он оптимизирован для операций на обоих концах).

Answer 4

Поскольку у меня было время, я бы делал это, используя набор и список.Список просто отслеживать последние n вставленных элементов.Также реализовано общее стирание.Для лучшей производительности (если вы не используете тот факт, что набор упорядочен), вы можете рассмотреть возможность использования 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