limit the size of a std::set

Question

I have a short question about the std::set container. Right now I am feeding my set using the pushback function. Of corse the set becomes larger and larger for every push_back. I am only intrested in the latest 30 elements or so... The older elements can be deleted. So my idea is to limit the size of the set to 30 elements or so and by doing so getting rid of the unwanted older elements. However the set does not support a limit by default. I could check the size of the set once in a while and manually delet the excess elements. Is there a smarter way ?

Regards Lumpi

Answer 1

As a solution you can encapsulate the set data structure into a class and in that class control the elements count.

Answer 2

You'll need to build a LRU structure yourself. One way to do this would be to have a std::map and std::list pointing to each other's iterators. That is:

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 look up an entry in the map, move its associated list entry to the start of the list. When adding an entry to the map, create a new lru_entry, add it to both map and list, and update the iterators in the lru_entry structure. When the lookup map exceeds 30 entries, you can then use the lru list to quickly find the oldest entry.

You can find more suggestions on how to build a LRU list in this previous stackoverflow question.