本文借助leetcode中的一道题目，来介绍LRU的相关知识，以及如何实现它。
leetcode 146:
问题：运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制。它应该支持以下操作: 获取数据get和写入数据put。 获取数据get(key)：如果密钥(key)存在于缓存中，则获取密钥的值(总是正数), 否则返回-1。 写入数据put(key, value)：如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作?
LRU：最近最少使用缓存机制
其设计的原则依据：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。 假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7 0 1 2 0 3 0 4，开始时3个物理块均为空，那么LRU算法是如下工作的：
分析：通过以上的图示过程，我们解决该问题的关键就是：当满状态需要移除一个元素时，此时结合需要写入的数据值。 (1)待写入的值不存在: 则将最近最少使用的数据弹出(可以理解为最先写入的数据) (2)待写入的值存在: 即最近使用了一次，则将原来的位置的值移动到最新插入的位置(可以理解为"队列的末尾")。
利用vector + map实现：
class LRUCache { private: int size; vector<int> data; map<int, int> cache; //有一个容量限制 public: LRUCache(int capacity) { size = capacity; data.clear(); cache.clear(); } int get(int key) { //获取 或者返回-1 int pos = find(data.begin(), data.end(), key) - data.begin(); if(pos >= data.size()) return -1; data.erase(data.begin() + pos); data.push_back(key); return cache[key]; } void put(int key, int value) { //不在 写入 | 当出现内存量满的情况!!! //如果已经存在, 查找该节点 int pos = find(data.begin(), data.end(), key) - data.begin(); if(pos < data.size()) data.erase(data.begin() + pos); //满状态 else if(data.size() == size) data.erase(data.begin()); data.push_back(key); cache[key] = value; } };考虑到vector中查询的速度并不快，我们可以使用一个链表，在增删的的速度要快一些。
使用list + map:
class LRUCache { private: int size = 0; list<pair<int, int>> data; map<int, list<pair<int, int>>::iterator> cache; public: LRUCache(int capacity) { size = capacity; } int get(int key) { auto it = cache.find(key); //返回的是一个迭代器 if(it == cache.end()) return -1; int value = it->second->second; //使用了 需要进行更新 data.erase(it->second); data.push_front(make_pair(key, value)); cache[key] = data.begin(); return value; } void put(int key, int value) { auto it = cache.find(key); if(it != cache.end()){ //如果找到了 data.erase(it->second); } else if(data.size() == size){ //将链表尾部的移除 cache.erase(data.back().first); data.pop_back(); } //插入到队首位置 data.push_front(make_pair(key, value)); //map<> 中建立映射关系 cache[key] = data.begin(); //不是一个数，而是一个list<pair> } };自己实现一个双向链表+map
class node{ public: int key; int value; node* pre; node* next; node(int k, int v){ //构造函数 key = k; value = v; pre = NULL; next = NULL; } }; class DoubleLinkedList{ public: node* head; node* tail; DoubleLinkedList(){ head = new node(INT_MIN, INT_MIN); tail = NULL; } void delNode(node* target){ if(target == NULL) return; //如果其是尾部节点 if(target == tail){ tail = target->pre;// 前驱节点 } target->pre->next = target->next; //判断target->next是不是最后一个节点 if(target->next){ target->next->pre = target->pre; } target->next = NULL; //相当于释放该节点 target->pre = NULL; } void addNode(node* newNode){ //链表操作中，判断原有链表的情况 if(tail == NULL || tail == head){ tail = newNode; } //采用的是头插法 newNode->next = head->next; newNode->pre = head; if(head->next){ //一个节点移动要考虑它有前驱和后继两个指针，在操作时需要注意 head->next->pre = newNode; } head->next = newNode; } }; class LRUCache { private: int size, cursize; DoubleLinkedList data; map<int, node*> cache; public: LRUCache(int capacity) { size = capacity; cursize = 0; //当前双链表中节点的个数 } int get(int key) { if(!cache.count(key)) return -1; //无 //有 data.delNode(cache[key]); //先删除 data.addNode(cache[key]); //再插入该节点(双链表的头部) return cache[key]->value; } void put(int key, int value) { if(cache.count(key)){ //如果找到了 先删除再插入 data.delNode(cache[key]); data.addNode(cache[key]); cache[key]->value = value; //维持一个的 } else{ //新建一个节点 node* newNode = new node(key, value); cache[key] = newNode; //在map中建立映射关系 data.addNode(newNode); //插入新节点 cursize ++; if(cursize > size){ //超过了指定的大小 cache.erase(data.tail->key); // 根据数据链表的尾部节点的key值删除 data.delNode(data.tail); cursize --; } } } };以上就是这篇的内容，欢迎各位提出问题和意见，谢谢！
