Search code examples
algorithmcachingc++11stl

The complexity of the LRU cache algorithm

I have in front of me a task to implement the LRU cache. And the longest operation in the system should take O(log (n)). As my Cache I use std :: MAP. I still need a second container for storing key + Creation Time - Sort by time. And when I need to update the address to the cache it should take somewhere:

  • Find by key O(log (n)).
  • Remove to an iterator O(1).
  • Insert a new element of the O(log (n)).

The oldest member must reside naturally in container.begin().

I can use only STL.

List - does not suit me.

list.find() - O (n)

Priority Queue - delete items not implemented.

I think it could ideally be stored in a std::set;

std::set<pair<KEY, TIME>>;

Sort std::set:

struct compare
{
    bool operator ()(const pair<K, TIME> &a, const pair<K, TIME> &b)
    {
        return a.second < b.second;
    }
};

And to find a key in std :: set to write the function wich looks for the first element of the pair - std::set<pair<KEY, TIME>>;.

What do you think? Can anyone tell if this suits my specified complexity requirements?

Solution

  • Yes you can use map plus set to get the complexity of deleting/updating/inserting as O(logn).

    1. map stores key,value pair.

    2. set should store time,key in this order ( you have done opposite ). When cache is full and you want to remove a key it will be correspong to the element in set to which it = myset.begin() points to.

    Having said that you can improve performance by using hash + double linked list.