题目：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
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.
解题思路：
利用双向链表+hashtable实现
Cache中的存储空间往往是有限的，当Cache中的存储块被用完，而需要把新的数据Load进Cache的时候，我们就需要设计一种良好的算法来完成数据块的替换。LRU的思想是基于“最近用到的数据被重用的概率比较早用到的大的多”这个设计规则来实现的。
为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度）。这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没有被使用的内容就向链表的后面移动。当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满时，淘汰链表最后的位置就是了。
查找一个链表中元素的时间复杂度是O(n)，每次命中的时候，我们就需要花费O(n)的时间来进行查找，怎么样才能提高查找的效率呢？当然是hashtable了，因为它的查找时间复杂度是O(1)。
实现代码：
#include <iostream>
#include <unordered_map> using namespace std;
/*
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. 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.
*/ //双向链表节点
struct LRUNode
{
int key;
int val;
LRUNode *pre;
LRUNode *next;
LRUNode(int k = , int v = ):key(k), val(v),pre(NULL), next(NULL){
}
};
class LRUCache{
public:
LRUCache(int capacity):cap(capacity),size() {
head = new LRUNode();
tail = new LRUNode();
head->next = tail;
tail->pre = head; } int get(int key) {
LRUNode *t = hashtable[key];
if(t)//key在hashtable存在，则调整该key在链表中对应节点的位置，将其插入到最前面
{
//分离t节点
t->pre->next = t->next;
t->next->pre = t->pre;
//将t节点插入到头结点之后，即第一个数据节点
t->pre = head;
t->next = head->next;
head->next = t;
t->next->pre = t;
return t->val; }
else
return -; } void set(int key, int value) {
LRUNode *t = hashtable[key];
if(t)//key在hashtable存在，则更新value及调整该key对应节点在链表中位置，将其插入到第一个节点
{
t->val = value;
//分离t节点
t->pre->next = t->next;
t->next->pre = t->pre;
//将t节点插入到头结点之后，即第一个数据节点
t->pre = head;
t->next = head->next;
head->next = t;
t->next->pre = t;
return ; } if(size == cap)//如果双向链表容量已满即缓存容量已满，则将最近不使用的节点即链表最后一个数据节点删除
{
LRUNode *tmp = tail->pre;
tail->pre->pre->next = tail;
tail->pre = tmp->pre;
hashtable.erase(tmp->key);
delete tmp;
size--;
} //创建key对应的一个新节点，插入到最前面
LRUNode *node = new LRUNode(key, value); node->pre = head;
node->next = head->next;
head->next = node;
node->next->pre = node; hashtable[key] = node;//在hashtable添加key对应的表项 size++;//链表节点数++ }
private:
int cap;//链表容量即缓存容量
int size;//缓存当前使用量
LRUNode *head;//链表头结点，不存数据，
LRUNode *tail;//链表尾节点，不存数据
unordered_map<int,LRUNode*> hashtable;//hashtable，用作查找O(1)时间复杂度 };
int main(void)
{
LRUCache lrucache();
lrucache.set(,);
lrucache.set(,);
lrucache.set(,);
lrucache.set(,);
cout<<lrucache.get()<<endl;
cout<<lrucache.get()<<endl;
cout<<lrucache.get()<<endl; return ;
}