LRU Cache
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.
思路:
维护两个结构。一个红黑树结构用于O(log N)搜索,另一个链表用于排列最新访问的数据。
几个值得注意的地方。std::list::remove会遍历每个元素,并删除符合条件的元素。而在程序中元素的值是唯一的,所以应该调用std::find,然后做std::list::erase。另外用了unordered_map,这样平均访问时间是O(1),用来通过一些消耗时间较长的测试用例。但是反过来占用了大量内存。
题解:
class LRUCache { int m_Capacity; unordered_map<int, int> m_Cache; list<int> m_Recently; void touch(int key) { auto kiter = find(begin(m_Recently), end(m_Recently), key); m_Recently.erase(kiter); m_Recently.push_front (key); } public: LRUCache (int capacity) : m_Capacity (capacity) {} int get (int key) { auto iter = m_Cache.find (key); if (iter == end(m_Cache)) return -1; // not found else { touch(key); return iter->second; } } void set (int key, int value) { auto iter = m_Cache.find (key); if (iter == end(m_Cache)) { if (m_Cache.size() >= m_Capacity) { int last = m_Recently.back(); m_Recently.pop_back(); m_Cache.erase (last); } m_Recently.push_front(key); } m_Cache[key] = value; touch(key); } };