限制 std::set 的大小

Question

我对std::set容器有一个简短的问题。目前我正在使用pushback函数填充我的集合。当然，每个push_back都会使集合变得越来越大。 我只对最近的30个元素感兴趣... 旧元素可以被删除。因此，我的想法是将集合的大小限制为大约30个元素，并通过这样做摆脱不需要的旧元素。然而，默认情况下，该集合不支持限制大小。我可以偶尔检查集合的大小并手动删除多余的元素。 有更聪明的方法吗？ 谢谢，Lumpi

- Lumpi

---

可能是生产代码中LRU实现的重复问题。 - bdonlan

Answer 1

作为一种解决方案，您可以将set数据结构封装到一个类中，并在该类中控制元素计数。

- Incognito

Answer 2

你需要自己构建一个LRU结构。一种方法是使用std::map和std::list相互指向各自的迭代器，即:

```html

您需要自行构建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列表快速查找最旧的条目。

您可以在这个之前的stackoverflow问题中找到更多有关如何构建LRU列表的建议。

- bdonlan

Answer 3

该集合不仅不支持限制，也不告诉您元素的年龄。创建一个封装容器的新类。该类可以提供方法，在添加元素时强制执行大小限制或显式地执行。如果基于添加元素的时间进行删除操作（它针对两端的操作进行了优化），则队列是理想的选择。

- Oswald

---

谢谢大家...我会尝试使用LRU建议！ - Lumpi

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

- H Briceno