Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class LRUCache {
- private:
- int maxSize;
- list<pair<int,int> > cache;
- unordered_map<int, list<pair<int,int> >::iterator> m;
- public:
- LRUCache(int capacity): maxSize(capacity) {
- }
- int get(int key) {
- auto it = m.find(key);
- if(it == m.end()){
- return -1;
- }
- cache.push_front(*(it->second));
- cache.erase(it->second);
- m[key] = cache.begin();
- return it->second->second;
- }
- void put(int key, int value) {
- auto it = m.find(key);
- if(it != m.end()){
- cache.erase(it->second);
- }
- cache.push_front({key,value});
- m[key] = cache.begin();
- if(cache.size() > maxSize){
- auto it = cache.rbegin();
- m.erase(it->first);
- cache.pop_back();
- }
- }
- };
- /**
- * Your LRUCache object will be instantiated and called as such:
- * LRUCache* obj = new LRUCache(capacity);
- * int param_1 = obj->get(key);
- * obj->put(key,value);
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement