首页 > 代码库 > LRU Cache
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.
1 struct cacheNode 2 { 3 int key; 4 int data; 5 }; 6 7 class LRUCache{ 8 public: 9 10 11 LRUCache(int capacity) 12 {13 size = capacity;14 }15 16 int get(int key) 17 {18 if( cacheMap.find(key) != cacheMap.end() )19 {20 list<cacheNode>:: iterator it = cacheMap[key];21 cacheList.splice(cacheList.begin(), cacheList, it);22 cacheMap[key] = cacheList.begin();23 return cacheList.begin()->data;24 }25 else26 return -1;27 }28 29 void set(int key, int value) 30 {31 if( cacheMap.find(key) != cacheMap.end() )32 {33 list<cacheNode>::iterator it = cacheMap[key];34 cacheList.splice(cacheList.begin(), cacheList, it);35 cacheMap[key] = cacheList.begin();36 cacheList.begin()->data =http://www.mamicode.com/ value;37 }38 39 else40 {41 if(cacheList.size() == size)42 {43 cacheMap.erase(cacheList.back().key);44 cacheList.pop_back();45 }46 47 cacheNode node;48 node.key = key;49 node.data =http://www.mamicode.com/ value;50 cacheList.push_front(node);51 cacheMap[key] = cacheList.begin();52 }53 }54 55 private:56 int size;57 list<cacheNode> cacheList;58 unordered_map<int, list<cacheNode>::iterator> cacheMap;59 };
LRU Cache
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。