前言：
因为自己查阅文章时经常遇到，这些问题：因为环境不同而导致结果不一致、因为文章跳跃度太大而导致无法理解、因为文章代码运行结果不同而苦恼。
所以为了看我文章的人不会遭遇同样的问题，
以后我的文章将遵循以下原则：
1.会在文章开头标明相关配置与环境
2.尽可能循序渐进（还是看不懂可能是我没有这样的天赋），标出阅读的前提知识
3.列出的代码自己先跑一遍
////////////////////////////////////////
语言：c++
前提知识：
1.map
2.queue
集成开发环境：Visual Studio 2017
////////////////////////////////////////
最近在虎牙一面时，被面试官问到的一道算法题——使用map为容器实现LRU算法。
LRU，Least Recently Used，最近最少使用页面换出算法，常用于页面置换算法，是为虚拟页式存储管理服务的。
当时第一想法是加上个序号，然后遍历map将序号小的换出，所以就想着将序号作为键，但是当时就被指出这样就抹杀了map的优势无法快速找到所需页面。
然后又想着另开一个队列存储相应的键，容量超出时先进的键当然先出，但是这样又有一个问题，还是当页面重复使用时它必须重新回到队尾，而无法快速找到重复页面键的这一想法被否决了。
当时还是太年轻了，过于紧张脑子一片空白，想了个低效的方法，再开一个map，使用页面的键来存页面最近使用的时间顺序，这样能快速更新序号，但是换出页面时还是得遍历这个存储序号的map太过于低效。
现在仔细想想，还是非常简单的问题，虽说可能不是最好的解决方法，但比起上面的方法还是比较有效率的。
思路：
使用结构体将页面数据包起来的同时加上使用计数，map存储这个结构体，另开一个队列，当页面被使用则将键值入队，当map满了后则不断出队，每次出队就对键值相应的Mydata使用计数-1，当使用计数归0时从map中删除，直至map有空余的容量。
下面为伪代码：
struct Mydata
{
size_t num;//使用计数
int data;//存储数据
Mydata(size_t _num) :num(_num), data(1) {}
};
int main()
{
using omap = std::unordered_map<int, Mydata>;
omap _map;
omap::iterator it;
std::queue<int> que;
while(...)
{
/*
获取页面
计算使用页面键值为x
*/
if(it=_map.find(x)！=_map.end())//页面是否在map中
//++it->second.num;//是则使用次数+1
else _map.insert(std::make_pair<int,Mydata>(x,Mydata(1)));否则页面插入map中
//que.push(x);键值插入queue中
while(_map.size()>=页面容量)//直到map空出空间
{
it = _map.find(que.front());
if (!--it->second.num)_map.erase(it);//使用次数归0则删除
que.pop();
}
}
return 0;
}
总结：
当初想利用shared_ptr的自定义deleter和引用计数来实现上述算法，但是发现只有复制share_ptr复制时引用计数才会自增，就算存储的指针数值一样引用计数也不会自增，所以最后自己使用了一个结构体来进行使用计数，实现最近未使用的页面换出。
如果还有什么更高效的算法，请在评论中告诉我，感谢阅读
