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

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.

Answer 2

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

Answer 3

The set not only does not support a limit, it also does not tell you the age of the element. Create a new class that encapsulates a container. That class can then provide methods to enforce the size limit when adding elements or explicitly. A queue would be ideal if removing is done based on when the element was added (it is optimized for operations at both ends).

Answer 4

Since I had the time, I would do it using a set and a list. The list just keep track of the last n inserted elements. Also implemented a general erase. For better performance (if you are not taking advantage of the fact that set is ordered) you may consider using unordered_set. (replace include <set> with include <unordered_set> as well as 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