提问人：Lumpi 提问时间：1/30/2011 最后编辑：bdonlanLumpi 更新时间：3/7/2016 访问量：4918
限制 std：：set 的大小
limit the size of a std::set
问：
我有一个关于 std：：set 容器的简短问题。现在我正在使用推回功能为我的套装喂食。对于每个push_back，套装变得越来越大。 我只对最新的 30 个元素感兴趣......可以删除较旧的元素。因此，我的想法是将集合的大小限制在 30 个左右，并通过这样做来摆脱不需要的旧元素。但是，默认情况下，该集不支持限制。我可以偶尔检查一下集合的大小，并手动删除多余的元素。 有没有更聪明的方法？
问候 Lumpi
答：
3赞
bdonlan
1/30/2011
#1
您需要自己构建一个 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 列表的更多建议。
6赞
Incognito
1/30/2011
#2
作为解决方案，您可以将数据结构封装到一个类中，并在该类中控制元素计数。set
1赞
Oswald
1/30/2011
#3
该集合不仅不支持限制，也不会告诉您元素的年龄。创建一个封装容器的新类。然后，该类可以提供在添加元素时或显式强制执行大小限制的方法。如果根据元素的添加时间进行删除，则队列将是理想的选择（它针对两端的操作进行了优化）。
评论
0赞
Lumpi
1/30/2011
谢谢大家...我会用 LRU 的建议来尝试！
0赞
H Briceno
3/2/2016
#4
既然我有时间，我会用一套和一份清单来做。该列表仅跟踪最后插入的 n 个元素。还实现了一般擦除。为了获得更好的性能（如果您没有利用订购集的事实），您可以考虑使用unordered_set。（替换为 以及include <set>include <unordered_set>std::setstd::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
评论