最近面试遇到不少自己不会的面试题，为了防止以后再遇到，所以记录下来 这次遇到的是LRU算法的实现，LRU是用于内存管理的一种页面置出算法，意为最近最少使用，用于将内存中经常不适用的页面置出内存，放入到外存或者对换区，使得其他可使用的页面进入内存 主要的操作是get/put,这篇实现完全照抄于博客：博客 所有的代码都没怎么改变，主要是我将自己的理解写在上面并做了一些测试，感兴趣的可以去大佬的博客，我这里主要是做一下记录，不是原创，如果有涉及到侵权请作者联系删除，下面贴代码：
class LRUCache { public: LRUCache(int capacity) :cap_(capacity), size_(0) {} int get(int key) { if (key2pos_.find(key) != key2pos_.end()) { //说明存在 put(key, key2pos_[key]->second); //这一步实际上是将最近访问得结点移到队列头部 见下put函数 return key2pos_[key]->second; //返回对应得头部 } return -1; } void put(int key, int value) { if (key2pos_.find(key) != key2pos_.end()) { //若结点已经存在 data_.erase(key2pos_[key]); //替换为最新的 后面会移动到list首部 --size_; } else if (size_ > cap_) { //超过容量则删除最后的结点 key2pos_.erase(data_.back().first); //删除 data_.pop_back(); --size_; } data_.push_front({ key, value }); //链表首部 key2pos_[key] = data_.begin(); //映射 ++size_; } void print() { for (auto &w : data_) { cout << w.first << ":" << w.second << endl; //打印的结果是最新插入的结果在最前面 } cout << endl; } private: int cap_; int size_; list<pair<int, int>> data_; //list存储 unordered_map<int, list<pair<int, int>>::iterator> key2pos_; //哈希映射 };一些测试结果：
int main() { LRUCache lru(10); lru.put(1, 2); lru.put(3, 4); lru.put(5, 6); lru.print(); //原始打印出应该是按插入的逆序 lru.get(1); //获取一个key-value由于 是最近被使用所以应该移动到头部 lru.print(); //将上面的get的key-value最先打印 其他顺序不变 }主要使用list来存储结点，最近使用的和get后的移动到头部，最少使用的放在尾部，使用unordered_map进行位置映射
从结果看到，进行put后，最先打印的是最后放进去的，进行一次get操作，get到的key-value就放在头部
