题目：
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操作。
get(key) -给定某个值value的键key。如果key在缓存中存在，返回它的value。否则返回-1.
set(key , value) -重置或者插入键值（如果键值不存在）。如果缓存达到它的容量，在插入新键值之前，，要删除最近最久未使用的键值。
思路：
1、采用链表保存key-value对，链表头表示最新访问或者插入的key-value，表尾表示最久未使用的。
如果get一个key或者set一个key-value，则把对应的key-value从链表中间移到链表头表示最近刚使用过，则最久未使用的key-value自然落到了链表尾部。
使用list特有的splice函数实现这个操作。
splice函数简介如下：
list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list。
函数有以下三种声明：
void splice ( iterator position,list<T,Allocator>& x );void splice ( iterator position,list<T,Allocator>& x, iterator i );void splice ( iterator position, list<T,Allocator>&x, iterator first, iterator last );将链表x的元素移动到目的list的指定位置position之前，高效的将他们插入到目的list并。
目的list的大小会增加，增加的大小为插入元素的大小。x的大小相应的会减少同样的大小。
2、然后采用哈希表保存key-value的位置。
代码：class LRUCache{public:LRUCache(){}LRUCache(int capacity):capacity(capacity){}int get(int key){if(cache.find(key) == cache.end())return -1;items.splice(items.begin(), items, cache[key]); //更新访问结点的位置，置于链表头部return cache[key]->second;}void set(int key, int value){if(cache.find(key) == cache.end()){//如果要插入的值不在缓存中，则把它插入到链表头，然后更新cache中的迭代器if(capacity == cache.size()){int tmp = items.back().first; //取得表尾items.pop_back(); //删除链表中的表尾cache.erase(tmp); //删除缓存中的表尾}items.push_front(make_pair(key , value)); //把新值插入到链表头cache[key] = items.begin();//添加新值到缓存中}else{cache[key]->second = value;//如果已存在key，则更新它的值items.splice(items.begin(), items, cache[key]);//更新结点的位置，置于链表头部}}private:list<pair<int , int> >items; //key-value链表，表头是最新结点，表尾是最久未使用结点，当有新结点访问或者插入时，放到表头unordered_map<int , list<pair<int , int> >::iterator >cache; //key代表key，value是key-value结点的位置int capacity;};
版权声明：转载请注明出处。
旅行，重复一个承诺和梦想，听他第二十八次提起童年往事，
