LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
- 新数据插入到头部；
- 每当缓存命中（即缓存数据被访问），则将数据移到头部；
- 当表满的时候，将表尾部的数据丢弃
class l{
private:
int len_;
std::deque<int> l_;
std::unordered_map<int,int>m_;
public:
explicit l(int s);
void set(int k,int v);
int get(int k);
};
l::l(int s):len_(s)
{
l_.resize(len_);
}
void l::set(int k,int v) {
auto i = std::find(l_.begin(), l_.end(), k);
if (i!=l_.end()){
std::remove(l_.begin(), l_.end(), k);
l_.push_back(k);
}
else{
l_.push_front(k);
m_.erase(l_.at(len_));
l_.pop_back();
m_.insert(std::make_pair(k,v));
}
}
int l::get(int k) {
auto i = std::find(l_.begin(), l_.end(), k);
if (i!=l_.end()){
l_.erase(i);
l_.push_front(k);
return m_.find(k)->second;
}
else{
//miss catch
}
return -1;
}
TEST(l,l)
{
l l1(5);
l1.set(1,1);
l1.set(2,2);
l1.set(3,3);
l1.set(4,4);
l1.set(5,5);
l1.set(6,6);
l1.get(1);
l1.get(3);
l1.get(2);
l1.get(3);
}