Limit the size of std :: set

Question

I have a short question about the std :: set container. Now I feed my set using the pushback function. From the roots, the set becomes larger and larger for each push_back. I am only interested in the last 30 elements or such ... Older elements can be deleted. Therefore, my idea is to limit the size of the set to 30 elements or in this way and get rid of unwanted old elements. However, the set does not support the default restriction. I could check the size of the set from time to time and manually delete the extra items. Is there a smarter way?

Regards Lumpy

Answer 1

You will need to build the LRU structure yourself. One way to do this would be to have std :: map and std :: list pointing to each other iterators. I.e:

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; 

Whenever you view an entry on a map, move its associated list entry to the top of the list. When adding an entry to the map, create a new lru_entry, add it to both the map and the list, and update the iterators in the lru_entry structure. When the search map exceeds 30 entries, you can use the lru list to quickly find the oldest entry.

You can find more suggestions on how to create an LRU list at fooobar.com/questions/93733 / ...

Answer 2

As a solution, you can encapsulate the set data structure in a class and control the number of elements in this class.

Answer 3

The set not only does not support the restriction, but also does not indicate the age of the element. Create a new class that encapsulates the container. This class can then provide methods to limit the size when adding elements or explicitly. The queue would be ideal if the deletion is based on when the item was added (it is optimized for operations at both ends).

Answer 4

Since I had time, I would do this using a set and a list. The list simply keeps track of the last n items inserted. Also implemented a general deletion. To improve performance (if you are not using the fact that the set is ordered), you can use unordered_set. (replace include <set> with include <unordered_set> , and also std::set with 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; } 

result:

 should see 2 3 elements: 2 elements: 3 should see 4 elements: 4