17370845950

LRU缓存用unordered_map+list实现：哈希表O(1)查key，链表O(1)维护时序；get时命中则移至头部并更新迭代器，未命中返回-1；put时存在则更新并前置，不存在且满容则删尾部再头插。

用C++实现LRU缓存，核心是让“最近最少使用”的元素自动被淘汰，关键在于快速查找 + 快速移动到最新位置。标准做法是：哈希表（unordered_map） + 双向链表（list）组合——哈希表提供O(1)查找，链表维护访问时序，且支持O(1)头插、尾删和任意节点摘除。

数据结构选型与设计逻辑

不能只用map或vector：map按key排序不反映访问顺序；vector删除中间元素是O(n)。而list是双向链表，erase一个迭代器是O(1)；unordered_map存key→list迭代器，就能在查到节点的同时，立刻把它移到链表头部（表示最新访问）。

缓存结构通常包含：

• 一个std::list<:p style="color:#f60; text-decoration:underline;" title="ai" href="https://www./zt/17539.html" target="_blank">air>：存(key, value)，头部为最新访问，尾部为最久未用
• 一个std::unordered_map::iterator>：通过key快速定位链表中对应节点
• 一个int capacity：最大容量，超限时删尾部节点

关键操作的实现要点

get(int key)：查map，存在则把对应节点移到list头部，更新map中该key的新迭代器，返回value；不存在返回-1。

put(int key, int value)：

• 如果key已存在：更新value，移到头部，更新map迭代器
• 如果key不存在：检查是否已达capacity；若已满，先删list尾部节点，并从map中擦除其key；再头插新节点，map中加入新映射

注意：list::push_front()返回新插入元素的迭代器，可直接存入map；用list::erase()删尾部时，要先用back().first拿到key再删map，否则迭代器失效后无法反查key。

完整可运行代码示例

以下是最简实用版本（省略异常处理，适合学习和面试）：

class LRUCache {
    int cap;
    list> cache; // {key, value}
    unordered_map>::iterator> map;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto it = map[key];
        int val = it->second;
        cache.erase(it);
        cache.push_front({key, val});
        map[key] = cache.begin();
        return val;
    }

    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            cache.erase(map[key]);
        } else if (cache.size() == cap) {
            int lastKey = cache.back().first;
            cache.pop_back();
            map.erase(lastKey);
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
};

调用示例：LRUCache lru(2); lru.put(1,1); lru.put(2,2); lru.get(1); lru.put(3,3); → 此时缓存含{3,3}和{1,1}，{2,2}被淘汰。

进阶优化与注意事项

实际工程中可考虑：

• 用std::shared_ptr管理节点，避免迭代器失效风险（但增加开销）
• 封装为模板类，支持任意key/value类型
• 加锁支持多线程（如mutable shared_mutex + scoped_lock）
• 避免重复构造pair：用cache.emplace_front(key, value)替代push_front({key,value})

不复杂但容易忽略：每次移动节点后必须更新map里的迭代器，否则下次get会解引用已失效的迭代器，导致崩溃。