How to implement a queue of unique ids where elements can be "bumped" to the top in C++?

user_6165833 0
Viewed 315

I am implementing a cache of elements (represented by unique ids), with a max number of elements to keep. Removing the last used element when I reach the max size. So it looks like a queue, but with unique elements, as I don't want to add multiple times the same id.

But the elements can be used more than once and should go back to the top of the queue when they get used again, so that the cache really deletes the element that was used the last.

I don't really know how to do this. My first guess is to use a std::list, so manage manually the uniqueness of the elements and the "move to the top" operation.
Is there any smarter way to achieve this?

Edit: I did not know the name but this is more or less Least recently used algorithms.

lru c++11 stl c++
3 Answers

It looks like this is a simple LRU cache problem. Here is some code that will help

class LRUCache { 
public:
LRUCache(const LRUCache& other) = delete;
LRUCache& operator=(LRUCache & other) = delete;       

LRUCache(int capacity) {   
    size = capacity;
}

int get(int key) {
    auto it = mp.find(key);
    if(it != mp.end())
    {
        int val = it->second.first;
        use(it);
        return val;
    }
    return -1;
}

void put(int key, int value) {
    auto it = mp.find(key);
    if(it != mp.end())
    {
        it->second.first = value;
        use(it);
        return;
    }

    if(mp.size() == size)
    {
        // evict
        mp.erase(lst.back());
        lst.pop_back();
    }
    // add new
    lst.push_front(key);
    mp[key] = {value,lst.begin()};  
}

private:
int size = 0;
unordered_map<int,pair<int,list<int>::iterator>> mp;
list<int> lst;

void use(unordered_map<int,pair<int,list<int>::iterator>>::iterator& it)
{
    lst.erase(it->second.second); // erase element from the list
    lst.push_front(it->first); // push key to front of the list
    it->second.second = lst.begin();
}
};
user_126097780

Perhaps you are looking for a std::set with a custom comparison operator?

I find an example for multiset here. Multiset allows duplicates, set doesn't, so this fits your bill better.

Drawing from the same idea, you can have a struct like so -

struct Elem
{
    std::string UID;
    std::chrono::time_point lastUsed;
}

And change the lastUsed parameter if you re-use an item in the cache.

user_30899080

We can do this in a combination of map and doubly linked liat.. If if ur ok with 2x space complexity.. then use a map where key is unique id and value is a pointer to node in doubly linked list. Doubly linked list will take care of the maintaining the last used id.. The map eliminates the duplicate unique id. If the cache size reaches a limit then find the first element in the doubly linked list and remove that unique id from the map and the remove the head element of the list. When a unique id is used then lookup in the value of id in map and move the node to the begining of the list.

user_761050
Related