Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
LeetCode上的原题，请参加我之前的博客LRU Cache。
class LRUCache{ public: // @param capacity, an integer LRUCache(int capacity) { size = capacity; } // @return an integer int get(int key) { auto it = m.find(key); if (it == m.end()) return -1; l.splice(l.begin(), l, it->second); return it->second->second; } // @param key, an integer // @param value, an integer // @return nothing void set(int key, int value) { auto it = m.find(key); if (it != m.end()) l.erase(it->second); l.push_front({key, value}); m[key] = l.begin(); if (m.size() > size) { int t = l.rbegin()->first; l.pop_back(); m.erase(t); } } private: int size; list<pair<int, int> > l; unordered_map<int, list<pair<int, int> >::iterator> m; };
本文转自博客园Grandyang的博客，原文链接：缓存器[LintCode] LRU Cache ，如需转载请自行联系原博主。