限制std :: set的大小

问题描述：

我有一个关于std :: set容器的简短问题。现在我正在使用推回功能喂养我的套装。对于每个push_back，集合变得越来越大。我只对最近的30个元素感兴趣......旧元素可以删除。所以我的想法是将设置的大小限制为30个元素左右，并通过这样做来摆脱不需要的旧元素。但是，默认情况下，该设置不支持限制。我可以一会儿检查一次设置的大小，然后手动删除多余的元素。有没有更聪明的方法？限制std :: set的大小

问候Lumpi

可能重复http://*.com/questions/2057424/ lru-implementation-in-production-code） – bdonlan 2011-01-30 13:20:03

答

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

你可以找到关于如何构建this previous * question.

答

一个LRU列表你可以封装set数据结构为一类，并在该类控制元件数的解决方案更多的建议。

答

该设置不仅不支持限制，它也不会告诉你元素的年龄。创建一个封装容器的新类。然后，该类可以提供方法来在添加元素时或强制执行大小限制。如果根据添加元素的时间（对两端操作进行了优化）进行删除，则队列将是理想的。

谢谢大家，我会试着用LRU的建议！ – Lumpi 2011-01-30 15:33:05

答

因为我有时间，我会用一套和一个列表来做。该列表只是跟踪最后n个插入的元素。还实施了一般擦除。为了获得更好的性能（如果您没有利用set命令的优点），可以考虑使用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

[在生产代码LRU实现]（的

限制std :: set的大小

相关推荐