Skip to content

Instantly share code, notes, and snippets.

@shahrajat

shahrajat/LRUCache.cpp

Last active December 26, 2015 21:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shahrajat/8cc8e525011e62eef10a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shahrajat/8cc8e525011e62eef10a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. shahrajat created this gist Dec 26, 2015.
    38 changes: 38 additions & 0 deletions LRUCache.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,38 @@
    class LRUCache{
    private:
    map<int,list<pair<int, int>>::iterator> keyToListItr; //key to list node*
    list<pair<int,int>> clist;
    int capacity;
    public:
    LRUCache(int capacity) {
    this->capacity = capacity;
    }

    int get(int key) {
    auto itr = keyToListItr.find(key);
    if(itr != keyToListItr.end())
    {
    clist.splice(clist.begin(),clist,itr->second); //move element to front
    return itr->second->second; //return the key value
    }
    return -1;
    }

    void set(int key, int value) {
    auto itr = keyToListItr.find(key);
    if(itr != keyToListItr.end()) //key exists
    {
    clist.splice(clist.begin(),clist,itr->second); //move element to front
    itr->second->second = value;
    return;
    }
    if(keyToListItr.size()==capacity) //already full, make space for new key, value
    {
    int del_key = clist.back().first;
    clist.pop_back();
    keyToListItr.erase(del_key);
    }
    clist.emplace_front(key, value);
    keyToListItr[key] = clist.begin();
    }
    };