C++ 实现 LRU Cache 缓存淘汰算法

什么是 Cache？

从硬件角度，Cache 是应用于速度不相同的两种存储介质之间的信息传输所应用到的硬件。

狭义的 Cache 指的是位于 CPU 和主存间的快速 RAM，通常它不像系统主存那样使用 DRAM 技术，而使用昂贵但较快速的 SRAM 技术。

广义上的 Cache 指的是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构。

除了 CPU 与主存之间有 Cache，内存与硬盘之间也有 Cache，乃至在硬盘与网络之间也有某种意义上的 Cache──称为 Internet 临时文件夹或网络内容缓存等。

Cache 基于局部性原理工作：

• 时间局部性：刚被访问的数据很可能再次被访问
• 空间局部性：一个位置被访问，其附近位置也可能被访问

在软件层面，Cache 是一种用空间换时间的策略，将计算结果或数据副本存储在快速访问的介质中。

Cache 的关键特性

硬件 Cache 的典型结构（以现代 CPU 为例）

• L1 Cache: 32KB 指令 + 32KB 数据，3-4 cycle 延迟
• L2 Cache: 256KB-512KB，10-12 cycle 延迟
• L3 Cache: 8MB-32MB，30-40 cycle 延迟
• 主内存：8GB-64GB，100-200 cycle 延迟

LRU Cache

介绍

LRU 是 Least Recently Used 的缩写，意思是最近最少使用，它是一种 Cache 替换算法。因此 LRU Cache 是一种缓存淘汰算法，当缓存容量满时，优先淘汰最久未使用的数据。

用途

1. 数据库缓存：MySQL 查询缓存
2. Web 服务器：缓存热点数据
3. 操作系统：页面置换算法
4. 应用层缓存：减少重复计算

特性

• 时间复杂度：O(1) 的插入、查找、删除
• 空间复杂度：O(n)
• 数据组织：维护访问顺序，最近访问的放头部，最久未访问的放尾部

实现

#pragma once
#include <iostream>
#include <unordered_map>
#include <list>
#include <utility>

  {
:
    }

    {
         it = map_.(key);
         (it == map_.())  ;
        
        nodes_.(nodes_.(), nodes_, it->second);
         it->second->second;
    }

    {
         it = map_.(key);
         (it != map_.()) {
            
            it->second->second = value;
            nodes_.(nodes_.(), nodes_, it->second);
            ;
        }
         (capacity_ <= ) ; 
         (<>(map_.()) == capacity_) {
            
             last = nodes_.();
            map_.(last.first);
            nodes_.();
        }
        
        nodes_.(key, value);
        map_[key] = nodes_.();
    }

:
     capacity_; 
    std::list<std::pair<, >> nodes_;
    std::unordered_map<, std::list<std::pair<, >>::iterator> map_;
};