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

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

С уважением Лумпи


c++ stdset lru
person Lumpi    schedule 30.01.2011    source источник
comment
возможный дубликат реализации LRU в производственном коде   -  person bdonlan    schedule 30.01.2011

Ответы (4)


arrow_upward
3
arrow_downward

Вам нужно будет построить структуру 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.

person bdonlan    schedule 30.01.2011

arrow_upward
6
arrow_downward

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

person Incognito    schedule 30.01.2011

arrow_upward
1
arrow_downward

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

person Oswald    schedule 30.01.2011
comment
Всем спасибо... Попробую с предложением LRU! - person Lumpi; 30.01.2011

arrow_upward
0
arrow_downward

Поскольку у меня было время, я бы сделал это, используя набор и список. Список просто отслеживает последние 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
person H Briceno    schedule 02.03.2016