题目

编写程序，设计并实现工业级常用的“最近最少使用”缓存淘汰算法 LRUCache。结合双向链表 std::list（维护访问时序，利用 splice 在 O(1) 内将活跃节点迁移至头部）与哈希表 std::unordered_map（存储 Key 到链表迭代器的映射，在 O(1) 内点对点寻址），实现 get 与 put 操作全流程时间复杂度严格为 O(1)。

输入格式：无需外部输入。

输出格式：输出缓存存取、热度更新与超出容量时的淘汰日志。

数据范围与约定：高频面试核心题、双向链表哈希复合数据结构设计。

思路与算法

1. 复合数据结构的必要性
数组查找慢，单向链表删除慢，哈希表无顺序性。唯有将哈希表与双向链表组合：哈希表保证 O(1) 查找，双向链表保证 O(1) 调整时序与淘汰末尾。

2. list::splice 的关键威力
当通过 get(key) 命中某个已有缓存项时，直接调用 cacheList.splice(cacheList.begin(), cacheList, it)，无需执行任何数据拷贝或节点的重新释放分配，瞬间将该节点置顶为最新。

3. 容量溢出淘汰
当 cacheList.size() > capacity 时，链表尾部的节点 cacheList.back() 即为最近最少使用节点。先在哈希表中擦除其 Key，再在链表中 pop_back()。

完整程序

#include <iostream>
#include <list>
#include <unordered_map>

class LRUCache {
private:
    int capacity_;
    // 双向链表存储键值对：头部是最近使用的，尾部是最近最少使用的
    std::list<std::pair<int, int>> items_;
    // 哈希表：存储 Key 到对应链表节点的迭代器
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map_;

public:
    explicit LRUCache(int cap) : capacity_(cap) {}

    int get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) {
            return -1; // 未命中
        }
        // 命中：利用 splice 在 O(1) 内将节点嫁接到链表最前端
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            // Key 已存在：更新值并刷新热度到最前端
            it->second->second = value;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }

        // 超出容量上限：淘汰末尾最久未访问的节点
        if (static_cast<int>(items_.size()) >= capacity_) {
            int evictKey = items_.back().first;
            map_.erase(evictKey);
            items_.pop_back();
            std::cout << "  [淘汰清理] 缓存已满，淘汰最久未用 Key: " << evictKey << "\n";
        }

        // 插入新节点到头部，并在哈希表中登记迭代器
        items_.emplace_front(key, value);
        map_[key] = items_.begin();
    }
};

int main() {
    LRUCache lru(2); // 容量为 2

    std::cout << "--- 1. 放入 Key 1 与 Key 2 ---\n";
    lru.put(1, 100);
    lru.put(2, 200);

    std::cout << "读取 Key 1: " << lru.get(1) << " (Key 1 变更为最新)\n\n";

    std::cout << "--- 2. 插入 Key 3 触发容量溢出淘汰 ---\n";
    lru.put(3, 300); // 此时最久未用的是 Key 2，Key 2 将被淘汰！

    std::cout << "尝试读取已被淘汰的 Key 2: " << lru.get(2) << " (期望为 -1)\n";
    std::cout << "读取活跃的 Key 3: " << lru.get(3) << "\n";
    std::cout << "读取活跃的 Key 1: " << lru.get(1) << "\n";

    return 0;
}

运行示例

输出：

--- 1. 放入 Key 1 与 Key 2 ---
读取 Key 1: 100 (Key 1 变更为最新)

--- 2. 插入 Key 3 触发容量溢出淘汰 ---
  [淘汰清理] 缓存已满，淘汰最久未用 Key: 2
尝试读取已被淘汰的 Key 2: -1 (期望为 -1)
读取活跃的 Key 3: 300
读取活跃的 Key 1: 100