#include <iostream>
#include <list>
#include <map>
#include <stack>
#include <queue>
using namespace std;
class LRUChache{
private:
struct elem{
int value;
};
int size;
typedef list<elem> mylist;
typedef map<int, mylist::iterator> myMap;
mylist list;
myMap map;
public:
LRUChache(int size){
this->size = size;
}
int get(int key){
auto it = map.find(key);
if(it == map.end()){return -1;}
else{
auto list_it = map[key];
int value = list_it->value;
elem elemm;
elemm.value = value;
list.erase(list_it);
list.push_front(elemm);
map[key] = list.begin();
return list.begin()->value;
}
}
void put(int key,int value){
auto it = map.find(key);
//找不到要分满和不满两种情况
if(it == map.end()){
if (list.size()==size){
map.erase(list.back().value);
list.pop_back();
}
list.push_front(elem{value});
map[key] = list.begin();
// 找到直接调整顺序就可以了
}else{
auto list_it = map[key];
elem ee;
ee.value = value;
list.erase(list_it);
list.push_front(ee);
map[key] = list.begin();
}
}
};
LRU C++ map+list 实现
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Set对每个对象只接受一次，并使用自己内部的排序方法(通常，你只关心某个元素是否属于Set,而不关心它的顺序--否...
- Android NDK开发之旅 目录 1.list-基本使用 执行代码 2.list-删除 执行代码 3.list...
- 前言： 详细介绍： List：元素有放入顺序，元素可重复Map：元素按键值对存储，无放入顺序Set：元素无放入顺序...
- 一 目的 在编写程序时，本人使用第二多的数据结构是键值对，通过唯一的key来索引一个可以更加“精密”数据结构。总结...
