LRU 缓存与堆的 C++ 实现

LRU 缓存

LRU（Least Recently Used，最近最少使用）缓存的规则是：每次访问或更新一个 key，就将它标记为“最近使用”；容量满时淘汰最久没有访问的 key。

要同时满足高效查找与高效调整访问顺序，经典组合是：

• std::unordered_map<Key, ListIterator>：由 key 直接定位链表节点，平均 O(1) 查找；
• std::list<std::pair<Key, Value>>：双向链表维护访问顺序，头部是最近使用（MRU），尾部是最久未使用（LRU）；已知节点时移动与删除都是 O(1)。

unordered_map 的最坏复杂度会因严重哈希冲突退化到 O(n)，所以这里的 O(1) 指平均复杂度。

实现

下面以 int 为 key/value。泛型版本只需将 int 替换为模板参数并提供合适的哈希函数。

#include <list>
#include <stdexcept>
#include <unordered_map>
#include <utility>

class LRUCache {
public:
    explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
        if (capacity == 0) {
            throw std::invalid_argument("capacity must be positive");
        }
    }

    // 命中时返回 value；未命中返回 false。
    bool get(int key, int& value) {
        auto map_it = index_.find(key);
        if (map_it == index_.end()) {
            return false;
        }

        // splice 在 O(1) 时间把已知节点移到链表头，迭代器仍然有效。
        items_.splice(items_.begin(), items_, map_it->second);
        value = map_it->second->second;
        return true;
    }

    void put(int key, int value) {
        auto map_it = index_.find(key);
        if (map_it != index_.end()) {
            // key 已存在：更新值并标记为最近使用。
            map_it->second->second = value;
            items_.splice(items_.begin(), items_, map_it->second);
            return;
        }

        if (items_.size() == capacity_) {
            // 尾部是最久未使用元素：先从哈希表删，再删除链表节点。
            const int lru_key = items_.back().first;
            index_.erase(lru_key);
            items_.pop_back();
        }

        items_.emplace_front(key, value);
        index_[key] = items_.begin();
    }

private:
    using Item = std::pair<int, int>;
    using Iterator = std::list<Item>::iterator;

    std::size_t capacity_;
    std::list<Item> items_;                    // 头 MRU，尾 LRU
    std::unordered_map<int, Iterator> index_; // key → 节点
};

使用示例：

LRUCache cache(2);
cache.put(1, 100); // [1]
cache.put(2, 200); // [2, 1]，2 最新

int value;
cache.get(1, value); // value = 100，顺序变为 [1, 2]
cache.put(3, 300);   // 淘汰 2，顺序为 [3, 1]

复杂度与易错点

操作	平均复杂度	原因
get	O(1)	哈希查找 + list::splice
更新已有 key	O(1)	哈希查找 + 移到表头
插入新 key	O(1)	头插；满容量时尾删
空间	O(capacity)	哈希表和链表各保存一份索引/节点信息

• 不能只用 vector 保存顺序：中间移动元素通常是 O(n)；
• 不能只用 unordered_map：它不保存“最近使用顺序”；
• 上述实现不是线程安全的。多线程同时调用 get/put 时，要在外部或类内部加 mutex；
• 高性能缓存还可能需要 TTL、分片锁、淘汰统计、容量按字节计算等能力。

堆与优先队列

**堆（heap）**是满足堆序性质的完全二叉树，通常用连续数组（std::vector）存储：

父节点 i：左孩子 2*i + 1，右孩子 2*i + 2

• 大顶堆：父节点不小于子节点，堆顶是最大元素；
• 小顶堆：父节点不大于子节点，堆顶是最小元素。

插入时将新元素放到末尾并向上调整（sift up）；删除堆顶时将末尾元素放到堆顶并向下调整（sift down）。因此插入和弹出堆顶为 O(log n)，查看堆顶为 O(1)。

首选：std::priority_queue

#include <functional>
#include <queue>
#include <vector>

// 默认大顶堆：top() 是最大元素。
std::priority_queue<int> max_heap;
max_heap.push(3);
max_heap.push(1);
max_heap.push(5);
int largest = max_heap.top(); // 5
max_heap.pop();               // 删除 5，O(log n)

// 小顶堆：top() 是最小元素。
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(3);
min_heap.push(1);
min_heap.push(5);
int smallest = min_heap.top(); // 1

自定义元素时，为 priority_queue 的第三个模板参数提供比较器。注意比较器表达的是“a 的优先级是否低于 b”：

#include <queue>
#include <string>
#include <vector>

struct Task {
    int priority;       // 数值越小，优先级越高
    std::string name;
};

struct HigherPriority {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority; // a 更靠后，形成小顶堆
    }
};

std::priority_queue<Task, std::vector<Task>, HigherPriority> tasks;
tasks.push({10, "normal"});
tasks.push({1, "urgent"});
Task next = tasks.top(); // {1, "urgent"}

堆算法：复用 vector

当需要查看或操作底层数组时，可以直接使用 <algorithm> 的堆算法：

#include <algorithm>
#include <vector>

std::vector<int> values{4, 1, 7, 3};
std::make_heap(values.begin(), values.end()); // 建大顶堆，整体 O(n)

values.push_back(9);
std::push_heap(values.begin(), values.end()); // 新末尾元素上滤，O(log n)

std::pop_heap(values.begin(), values.end());  // 最大值移到末尾，O(log n)
int largest = values.back();
values.pop_back();                             // 真正移除末尾元素

std::pop_heap 只将堆顶交换/调整到区间末尾，不会缩短 vector，还需要调用 pop_back()。

常见应用与限制

场景	堆顶含义
Top K	维护大小为 K 的小顶堆，堆顶是当前第 K 大候选
定时器	小顶堆按触发时间排序，堆顶是最近到期任务
任务调度	堆顶是最高优先级任务
匹配队列	按价格、时间或优先级选取下一候选

标准 priority_queue 不支持高效删除/更新任意位置元素；如定时器任务被取消或优先级改变，常采用延迟删除（弹出时检查任务版本/取消标记），或使用“key → 堆下标”的索引堆实现。也要注意堆只保证堆顶最优，内部元素不是完全排序的，不能把它当作有序容器遍历。