C++实现LRU算法_c++ 最简单实现lru

LRU算法

LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。LRU算法的提出，是基于这样一个事实：已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。因此，我们只需要在每次调换时，找到最近最久未使用的那个页面调出内存。这就是LRU算法的全部内容。

实现

使用双向链表和哈希表实现LRU算法

• 双向链表用于保存key-value，队头的元素表示最近一次被访问的元素，队尾的元素表示最近最久未使用的元素
• 哈希表提供key到key对应节点在双向链表中的位置的映射

实现了get操作和put操作

• get：传入key，得到value，并将对应节点移动到双向链表头部（因为这个节点是最近被访问的节点）
• put：传入key-value对，分三种情况处理
  • 若key已存在，则先删除对应节点，再把key-value插入双向链表头部（因为这个节点是最近被访问的节点）
  • 若双向链表长度大于或等于最大元素个数，则删除双向链表队尾元素（最近最久未使用的元素），再把key-value插入双向链表头部
  • 若上面两个条件不满足，只需要把key-value插入双向链表头部

与有的博客中实现方式不同的是，我用一个变量size_保存双向链表的长度，因为std::list的size方法是O(n)时间复杂度的（具体可看我另一篇转载的博客）。做了这个改进后，get和put的时间复杂度都为O(1)

代码实现

class LRUCache {
   
public:
    LRUCache(int capacity) : cap_(capacity), size
1
2
3