题目要求：
设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。
int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。
void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。
请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。
限制：请在O(1)的时间复杂度内完成上述2个操作。
输入描述
第一行读入一个整数n，表示LRU Cache的容量限制。 从第二行开始一直到文件末尾，每1行代表1个操作。
如果每行的第1个字符是p，则该字符后面会跟随2个整数，表示put操作的key和value。
如果每行的第1个字符是g，则该字符后面会跟随1个整数，表示get操作的key。
输出描述
按照输入中get操作出现的顺序，按行输出get操作的返回结果。
示例：
输入：
2
p 1 1
p 2 2
g 1
p 2 102
p 3 3
g 1
g 2
g 3
输出：
1
1
-1
3
解题思路：
put(key,value)在O(1)的时间内完成，可以使STD中的一个容器：双端链表list，由于list没有实现[]操作符重载，为了实现O(1)内查找，可以使用另一个容器：ordered_map。每次“使用”元素的时候，就将该元素调整到链表的首部，这样当超出容量的时候，直接删除链表末尾的元素及其在map中对应的值。
list介绍：
list是一种序列式容器。
list容器完成的功能实际上和双向链表极其相似，list中的数据元素是通过链表指针串连成逻辑意义上的线性表，也就是list也具有链表的主要优点，即：在链表的任一位置进行元素的插入、删除操作都是快速的。
由于list元素节点并不要求在一段连续的内存中，显然在list中是不支持快速随机存取的，因此对于迭代器，只能通过“++”或“–”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作，这点，是与vector等不同的地方。
begin() #返回一个指向容器起始位置的iteratorrbegin() #返回list中末尾的迭代器end() #返回list末端下一位置的iteratorpush_back() #插入元素到list的末尾push_front() #从list的头部插入元素empty() #判断list是否为空resize() #调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除，如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val)，则扩展元素要调用构造函数T(val)函数进行元素构造，其余部分相同clear() #清空list中的所有元素front() #返回list容器中的头部元素引用back() #返回list容器的最后一个元素的引用pop_back() #删除链表的末尾元素pop_front() #删除链表的首部元素swap() #交换两个链表,list1,swap(list2)和swap(list1,list2)都可以实现list1和list2的交换splice() #实现链表拼接/**将源list的内容部分或全部元素删除，拼插入到目的list，有三种函数声明dest_list.splice(iterator position,list<T,Allocator>& source_list) #将source_list的所有元素剪接到dest_list的position的后面dest_list.splice(iterator position,list<T,Allocator>& source_list, iterator it)#将source_list的it位置处的元素剪接到dest_list的position的后面dest_list.splice(iterator position,list<T,Allocator>& source_list, iterator first,iterator last)#将source_list的first到last的元素剪接到dest_list的position后面##测试#include<list>#include <iostream>using namespace std;int main(){list<int>list1,list2;for(int i=1;i<=4;i++) {list1.push_back(i);list2.push_back(i+10);}// list1 1 2 3 4// list2 11 12 13 14list<int>::iterator it=list1.begin();it++;list1.splice(it,list2);//1 11 12 13 14 2 3 4if(list2.empty()) cout<<"list2 is empty"<<endl;list2.splice(list2.begin(),list1,it);cout<<*it<<" "<<endl;/*list1 1 11 12 13 14 3 4list2 2这里的it的值还是2，但是指向的已经是list2中的了 */it=list1.begin();advance(it,3);//advance 的意思是增加的意思，就是相当于 it=it+3;这里指向13list1.splice(list1.begin(),list1,it,list1.end()); //13 14 3 4 1 11 12 可以发现it到list1.end()被剪贴到list1.begin()前面了 for(list<int>::iterator it=list1.begin();it!=list1.end();++it) cout<<*it<<" ";cout<<endl;for(list<int>::iterator it=list2.begin();it!=list2.end();++it) cout<<*it<<" ";cout<<endl;list<pair<int,int> > list3;for(i=1;i<=3;i++)list3.push_back(make_pair(i,i+3));list<pair<int,int> >::iterator iter=list3.begin();cout<<iter->first<<" "<<iter->second<<endl;return 0;} ##结果list2 is empty213 14 3 4 1 11 1221 4**/
unordered_map介绍
1、与map的区别
map的内部实现是红黑树（红黑树是一种严格的平衡二叉搜索树），因此该容器具有自动排序的功能，map内部的所有元素都是有序的。对map的所有操作都是基于红黑树，因此很多操作都可以在O(logn)的时间内完成，map适用于对元素顺序有要求的场合。
缺点：由于红黑树的节点需要保存节点指针和数据域，所以红黑树的空间开销比较大。
unorder_map的内部实现是哈希表，并且使用开放链表寻址法解决冲突问题，因此元素的查找速度可以达到O(1)，适用于对于查找操作有较高才做的场合。
缺点：哈希表的时间复杂度比较高。
2、使用
find(key) #返回key所对应的迭代器，如果该迭代器与end()相等，说明map中不存在key。count(key) #返回key在map中出现的次数，如果为0说明key不在map中iterator erase(const_iterator pos ) #移除map中pos处键值对iterator erase(const_iterator first, const_iterator last );#移除map中first到last的键值对size_type erase(const key_type& key )#移除特定key的键值对。begin() #返回指向容器起始位置的迭代器end() #返回指向容器末尾位置的迭代器 cbegin() #返回指向容器起始位置的常迭代器（const_iterator） cend() #返回指向容器末尾位置的常迭代器 insert() #插入元素 /**unordered_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值。unordered_map<Key,T>::iterator it;(*it).first; // the key value (of type Key)(*it).second; // the mapped value (of type T)(*it); // the "element value" (of type pair<const Key,T>) it->first;// 同 (*it).first (the key value)it->second; // 同(*it).second (the mapped value) **/
实现代码：
#include <iostream>#include <unordered_map>#include <list>#include <string>#include <sstream>using namespace std;class LRUCache{private:int cap;list<pair<int,int>> L;unordered_map<int,list<pair<int,int>>::iterator> m;public:LRUCache(int capacity){cap=capacity;}int get(int key){auto it=m.find(key);if(it == m.end()) return -1;L.splice(L.begin(),L,it->second);return it->second->second;}void put(int key,int value){auto it=m.find(key);if(it != m.end()) {it->second->second=value;}else{L.push_front(make_pair(key,value));m[key]=L.begin();}if(m.size() > cap){int k=L.rbegin()->first;L.pop_back();m.erase(k);}}};int main(){int n;cin>>n;LRUCache L(n);string cmd;char commond;while(getline(cin,cmd)){istringstream iss(cmd);iss>>commond;if(commond=='p'){int key,val;iss>>key>>val;L.put(key,val);}else if(commond=='g'){int key;iss>>key;int val=L.get(key);cout<<val<<endl;}}return 0;}
注意
按行读取输入，每一行的输入通过getline(cin,cmd)读入到cmd中，然后通过istringstream iss(cmd)构造一个字符串输入流，然后从中解析出字符、整数。
如果觉得《数据结构LRUCache(Least Recently Used – 最近最少使用缓存)》对你有帮助，请点赞、收藏，并留下你的观点哦！
