LRU(最近最少使用)是操作系统内存页面置换的一种技术
1.1 题目大意
①当内存满时，将最近最少使用的元素置换出去
②最近使用的元素(get和put函数调用的元素)，优先级最高
1.2 题目分析
为了调整当前内存中元素的优先级，可以设计类似于队列的形式，优先级高的(最近使用)放在最前面，优先级低的(最近未使用的)放在后面，当需要置换时，将优先级低的元素(最后面)置换出去，新增加的元素(最近使用)放在前面；为了在常数时间复杂度内，查找内存当中的元素，需采用hashtable存储内存当中的元素
借助双向链表list和hashtable(map)，list按照优先级的顺序存储当前内存中的元素，方便对元素的优先级进行重新排列；hashtable存储list元素中key所对应的list迭代器
2.1 get函数
①当所查找的key(最近使用)在内存当中，调整list中元素的优先级，即将key对应的元素放到list链表的最前面；
②若不在内存当中，返回-1;
2.2 put函数
①当新增加的元素已经在内存当中，重新调整list元素的优先级，同时更新hashtable中key所对应的指针；
②当不在内存当中，分为两种情况考虑：
当前内存还未满，将新增元素(优先级最高)放到链表list的最前面，并将key放到hash表当中；
当前内存已满，将list中最后一个元素置换出去，将新增元素(优先级最高)放到链表list的最前面，并将key放到hash表当中;
struct cacheNode{ int key; int value; cacheNode(int k, int v): key(k), value(v) { } }; class LRUCache { public: int capacity; //cache容量 list<cacheNode> cache; map<int, list<cacheNode>::iterator> exist; //记录当前在内存当中的key,value对应当前的key在list链表中的迭代器 LRUCache(int capacity) { this->capacity = capacity; } int get(int key) { if (exist.find(key) != exist.end()){ //内存当中存在该key list<cacheNode>::iterator it = exist[key]; cache.splice(cache.begin(), cache, it); //将list链表中it迭代器指向的节点放到头结点的位置 exist[key] = cache.begin(); //更新在字典当中key所对应的指针 return cache.begin()->value; } else{ return -1; } } void put(int key, int value) { if (exist.find(key) != exist.end()){ //该key存在内存当中，重新调整优先级 list<cacheNode>::iterator it = exist[key]; cache.splice(cache.begin(), cache, it); exist[key] = cache.begin(); //调整到最前面 cache.begin()->value = value; } else{ if (capacity == cache.size()){ //若内存已满，移除最后一个元素 exist.erase(cache.back().key); cache.pop_back(); } cache.push_front({key, value}); //将新的元素放在开始的位置，最近最少使用的优先级低 exist[key] = cache.begin(); } } }; /** * 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); */[1]https://www.cnblogs.com/x1957/p/3485053.html
