lk146
LRU缓存主要是实现get()和put()两个函数，均要求O(1)的时间复杂度
第一版get()函数是根据指定的key返回value,最初的做法是维护一个双链表list，然后根据key找value，找到的话，使用remove函数删除节点并重新插入最后面。这种做法存在疏漏，一是遍历操作会带来O(n)的时间复杂度，二来remove函数仅支持传入value,并且也会带来O(n)的时间复杂度（使用erase函数即可）
第一版的put函数思路如下，遍历list，如果元素存在的话先删除再插入最后面，和之前一样也是remove函数使用有误，外加遍历的复杂度过高；如果没找到，先判断是否满载，再按需插入
// 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
// 实现 LRUCache 类：
// LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
// 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
for (pair<int,int> iter : list) {
if (iter.first == key) {
int val = iter.second ;
// remove不能直接传迭代器进去，erase函数可以
list.remove(iter);
list.push_back(pair<int,int>(key,val));
return val ;
}
}
return -1;
}
void put(int key, int value) {
for (pair<int,int> iter : list) {
if (iter.first == key) {
list.remove(iter);
list.push_back(pair<int,int>(key,value));
return;
}
}
if (list.size() == cap) list.pop_front();
list.push_back(pair<int,int>(key,value));
}
private:
int cap ;
list<pair<int,int>> list;
};
以下是第二版
使用一个map存储从key到迭代器的映射，用空间换时间。
需要注意的是迭代器的写法unordered_map<int, list<pair<int, int»::iterator>
这里涉及一个新的函数splice，函数签名如下：void splice(const_iterator pos, list& other, const_iterator it)
功能是把第三个参数（迭代器）指向的元素，以O(1)的时间复杂度移动到第一个参数指定的位置
第二个参数other，顾名思义，该函数可以把当前list的迭代器指向的元素，移动到另一个list的指定位置
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
if (const auto it = key_to_iter.find(key); it != key_to_iter.end()) {
int val = it->second->second ;
cache.splice(cache.end() , cache , it->second) ;
key_to_iter[key] = --cache.end();
return val ;
}
return -1;
}
void put(int key, int value) {
if (auto it = key_to_iter.find(key); it == key_to_iter.end()) {
if (cache.size() == cap) {
key_to_iter.erase(cache.front().first);
cache.pop_front();
}
cache.push_back(pair<int,int>(key,value));
key_to_iter[key] = --cache.end();
} else {
it->second->second = value ;
cache.splice(cache.end() , cache , it->second) ;
key_to_iter[key] = --cache.end();
}
}
void print() {
for (pair<int,int> it : cache) {
cout << "key : " << it.first << " value : " << it.second << endl;
}
}
private:
int cap ;
list<pair<int,int>> cache;
unordered_map<int, list<pair<int, int>>::iterator> key_to_iter;
};