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

Question

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.

score 1 · Answer 1 · answered May 12 '20 at 08:31

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();
}
};

Sounds like the way to go, thx. Note that if the copy of the *element* is heavy, we could use `list::splice` to move it instead of `erase`+`push` (https://stackoverflow.com/a/4912492/6165833) — ymoreau, May 12 '20 at 09:08
splice has the same complexity though. Erasing element from a doubly linked list given a pointer is O(1), inserting to the head also O(1). All we are dealing here is pointers, so there is no construction/destruction — dgrandm, May 16 '20 at 22:04

score 1 · Answer 2 · answered May 12 '20 at 08:35

1

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.

answered May 12 '20 at 08:35

Roy2511

938
1
5
22

Sounds like a smart and concise solution. But that means the whole data-structure has to be reordered at each change/insertion right? – ymoreau May 12 '20 at 09:11
1

Yes, it's reordered at every change/insertion/deletion with O(log n) complexity. – Roy2511 May 12 '20 at 09:22

score 0 · Answer 3 · answered May 12 '20 at 08:51

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.

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

3 Answers3