Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:getandset.
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.
实现一个LRU的缓存，这实际上就是操作系统中内存管理的一种算法。最不经常使用算法，要求当内存使用完时先淘汰掉最久未使用的内存，这里模拟了两个对内存的操作，get和set。
因为要存储key和value，所以很明显需要使用一个map，但是map无法记录key的使用顺序，所以还需要一个能记录使用顺序的数据结构，这里可以使用vector和list，由于set操作是当key已经存在时替换当前的value，所以记录顺序的数据结构可能会有频繁的删除操作，那么需要舍弃掉vector，最后记录使用顺序的数据结构就需要使用list。
下面再分析get和set需要处理的事情：
get操作时，需要执行下面两步操作：
返回map中key对应的value；同时需要更新list中key的位置，将key放置在list中最近被访问的位置上，那么可以定义list中的首端(front)元素是最近被访问的元素。更新操作同样需要两部来完成：1：删除list中原来的key；2：将key插入list首端。
set操作会比较复杂一些：
上面是基本的操作步骤，按照这个方式编写的代码如下：
class LRUCache{private:int capacity;map<int,int> datas;list<int> s;public:LRUCache(int capacity) {this->capacity=capacity;}int get(int key) {auto iter=datas.find(key);if(iter!=datas.end()){update(iter);return iter->second;}elsereturn -1;}void set(int key, int value) {int length=datas.size();auto iter=datas.find(key);if(iter!=datas.end()){datas[key]=value;update(iter);}else{if(length>=capacity){datas.erase(s.back());s.pop_back();}s.push_front(key);datas[key]=value;}}private:void update(map<int,int>::iterator iter){int key=iter->first;s.remove(key);s.push_front(key);}};但是很悲剧的是这在leetcode中会显示超时，主要的原因就是从list中删除指定的key值使用的是remove函数，这个函数无法在常数时间内删除元素，它需要遍历整个list，那么解决这道题的难点现在就变成了如何在常数时间内删除list中的元素，可以发现erase就可以，，但是它需要的是一个迭代器，这里就要想到这道题是让我们设计一个数据结构了，可以将元素在list中的位置（即迭代器）保存在map中，这样当执行上面的更新update操作时，就可以在常数时间内删除list中的元素，那么如何使map在保存了key与value的情况下还保存一个迭代器呢？可以将map中的第二个元素定义成pair类型就可以了。这就是分析的思路。
下面是改进后的代码：
runtime:104ms
class LRUCache{private:typedef pair<int,list<int>::iterator> PILI;int capacity;map<int,PILI> datas;list<int> s;public:LRUCache(int capacity) {this->capacity=capacity;}int get(int key) {auto iter=datas.find(key);if(iter!=datas.end()){update(iter);return iter->second.first;}elsereturn -1;}void set(int key, int value) {int length=datas.size();auto iter=datas.find(key);if(iter!=datas.end()){iter->second.first=value;update(iter);}else{if(length>=capacity){datas.erase(s.back());s.pop_back();}s.push_front(key);datas[key]=PILI(value,s.begin());}}private:void update(map<int,PILI>::iterator iter){int key=iter->first;s.erase(iter->second.second);s.push_front(key);iter->second.second=s.begin();}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
海阔凭鱼跃，天高任鸟飞。我要加油，冲向我的理想。
