首页 > 代码库 > LRU Cache

LRU Cache

2024-07-16 21:11:08   224人阅读

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.

思路：使用map和list实现LRU cache，map能够加速查找速度，而list能够快速地动态插入和删除节点。

        每次若访问命中，即key存在于cache中，则将其对应的list中的元素移至list首部。然后，对于get，返回list首部元素的value值；对于set，修改list首部元素的value值。

        若访问未命中，对于get，返回-1；对于set，将新的“key-地址”映射和“key-value”值对分别插入map中和list的首部。

        若cache已达到容量上限，则插入新元素之后，应从list尾部删除一个元素，并将其key值对应的“key-地址”映射从map中删除。

 1 class Node 2 { 3  public: 4     Node(): key(-1), value(-1) {} 5     Node( int aKey, int aValue ): key(aKey), value(aValue) {} 6     int key; 7     int value; 8 }; 9 10 class LRUCache{11 public:12     LRUCache(int capacity) { this->capacity = capacity; }13     14     int get(int key) {15         if( cacheMap.find( key ) != cacheMap.end() ) {16             list<Node>::iterator iter = cacheMap[key];17             cacheList.splice( cacheList.begin(), cacheList, iter );18             cacheMap[key] = cacheList.begin();19             return cacheList.begin()->value;20         }21         return -1;22     }23     24     void set(int key, int value) {25         if( cacheMap.find( key ) != cacheMap.end() ) {26             list<Node>::iterator iter = cacheMap[key];27             cacheList.splice( cacheList.begin(), cacheList, iter );28             cacheMap[key] = cacheList.begin();29             cacheList.begin()->value =http://www.mamicode.com/ value;30         } else {31             if( cacheMap.size() == capacity ) {32                 cacheMap.erase( cacheList.back().key );33                 cacheList.pop_back();34             }35             cacheList.push_front( Node(key,value) );36             cacheMap[key] = cacheList.begin();37         }38     }39 40 public:41     int capacity;42     list<Node> cacheList;43     unordered_map<int,list<Node>::iterator> cacheMap;44 };

 


联系
我们