LRU Cache：哈希表 + 双向链表实现 O(1) 的最近最少使用缓存

#include <list>            // std::list：底层的双向链表
#include <unordered_map>   // std::unordered_map：底层的哈希表
#include <utility>         // std::pair、std::make_pair
#include <iostream>        // std::cout
using namespace std;
 
class LRUCache
{
public:
    // 构造：记录容量上限
    LRUCache(int capacity)
        : _capacity(capacity)   // 容量由外部传入，_list 和 _map 用默认构造即可
    {}
 
private:
    // _list 存的是 <key, value>，表头最近、表尾最久（方向契约）
    list<pair<int, int>> _list;
 
    // 容量上限，超过就淘汰表尾
    int _capacity;
 
    // 哈希表：key -> 该 key 在 _list 中对应结点的迭代器（指针桥接）
    // 有了这个迭代器，我们才能在链表里 O(1) 定位并删除/搬家
    unordered_map<int, list<pair<int, int>>::iterator> _map;
};

    // get：按 key 取值，命中并刷新为最近使用；未命中返回 -1
    int get(int key)
    {
        // 1. 在哈希表里找这个 key
        auto hashIt = _map.find(key);
 
        // 2. 未命中：返回哨兵值 -1
        if (hashIt == _map.end())
        {
            return -1;               // Cache Miss，缓存里没有
        }
 
        // 3. 命中：拿到该 key 在链表中的迭代器
        auto listIt = hashIt->second;   // 通过"桥"取得链表位置
 
        // 4. 把这个结点搬到链表头部，表示"刚刚又被使用了"
        //    步骤：先拷贝出数据 -> 在原位置删除 -> 头插 -> 重新登记迭代器
        pair<int, int> kv = *listIt;    // 解引用迭代器，得到 <key, value>
        _list.erase(listIt);            // 从原位置删除，旧指针作废
        _list.push_front(kv);           // 插到链表头部成为最新
        _map[key] = _list.begin();      // 重新登记：key 现在指向新的头部
 
        // 5. 返回值
        return kv.second;
    }

    // put：写入 <key, value>；key 已存在则更新并刷新，否则新增并可能淘汰
    void put(int key, int value)
    {
        // 1. 在哈希表里找这个 key
        auto hashIt = _map.find(key);
 
        // 情况 A：key 已经存在 -> 更新值，并搬到头部
        if (hashIt != _map.end())
        {
            auto listIt = hashIt->second;   // 通过桥拿到链表位置
            pair<int, int> kv = *listIt;    // 拷贝出原结点
            kv.second = value;              // 只改 value，key 不变
            _list.erase(listIt);            // 原位置删除（旧迭代器作废）
            _list.push_front(kv);           // 头插，记为最近使用
            _map[key] = _list.begin();      // 重新登记迭代器
            return;                         // 更新完成，直接返回
        }
 
        // 情况 B：key 不存在 -> 新增一个结点
        //    B1：如果已经满了，先淘汰表尾（最久未使用），给新数据腾位置
        if ((int)_list.size() >= _capacity)
        {
            // 注意：删除表尾时，必须同步删掉哈希表中该 key 的登记，
            //       否则哈希表里会残留一个"指向已删除结点"的失效迭代器
            _map.erase(_list.back().first);  // 取表尾结点的 key，从哈希表删除
            _list.pop_back();                // 再删链表的表尾结点
        }
 
        //    B2：插入新结点到头部，并在哈希表登记
        _list.push_front(make_pair(key, value));
        _map[key] = _list.begin();
    }

#include <unordered_map>   // std::unordered_map
#include <iostream>
using namespace std;
 
class LRUCache
{
private:
    // 双向链表结点：除了数据，还持有前后指针
    struct Node
    {
        int key;      // 键
        int value;    // 值
        Node* prev;   // 前驱指针
        Node* next;   // 后继指针
 
        // 构造函数：用 key/value 初始化，前后指针先置空
        Node(int k, int v)
            : key(k)
            , value(v)
            , prev(nullptr)
            , next(nullptr)
        {}
    };
 
    int _capacity;                       // 容量上限
    unordered_map<int, Node*> _map;      // 哈希表：key -> 链表结点指针
    Node* _head;                         // 头哨兵，不存数据；head->next 是最近使用
    Node* _tail;                         // 尾哨兵，不存数据；tail->prev 是最久未使用

    // 工具一：从双向链表中摘除一个结点（O(1)，因为用的是裸指针、无需找前驱）
    void removeNode(Node* node)
    {
        node->prev->next = node->next;   // 让前驱的 next 跳过当前结点
        node->next->prev = node->prev;   // 让后继的 prev 跳过当前结点
        // 注意：这里不 delete，只是"拆下来"，由调用方决定是否释放
    }
 
    // 工具二：把一个结点插到头部哨兵后面，表示"刚被使用"
    void insertFront(Node* node)
    {
        node->next = _head->next;        // node 的后继：原来的队首
        node->prev = _head;              // node 的前驱：头哨兵
        _head->next->prev = node;        // 原来的队首的前驱改为 node
        _head->next = node;              // 头哨兵的后继改为 node
    }
 
    // 工具三：把"已存在"的结点搬到头部 = 先摘除 + 再头插（仍然 O(1)）
    void moveToFront(Node* node)
    {
        removeNode(node);
        insertFront(node);
    }

public:
    // 构造：分配头尾哨兵并互连，初始时它俩形成空环链表（list 为空）
    LRUCache(int capacity)
        : _capacity(capacity)
        , _head(new Node(0, 0))   // 哨兵不存真实数据，(0,0) 只是占位
        , _tail(new Node(0, 0))
    {
        _head->next = _tail;   // 头哨兵的后继指向尾哨兵
        _tail->prev = _head;   // 尾哨兵的前驱指向头哨兵
    }
 
    // 析构：释放所有结点（包括哨兵），防止内存泄漏
    ~LRUCache()
    {
        Node* cur = _head;     // 从头部哨兵开始遍历
        while (cur)
        {
            Node* next = cur->next;  // 先记下后继，否则删除当前结点后指针就悬了
            delete cur;              // 释放当前结点
            cur = next;              // 顺着后继前进
        }
    }
 
    // get：命中则搬到头部并返回值；未命中返回 -1
    int get(int key)
    {
        auto it = _map.find(key);    // 哈希表找 key
        if (it == _map.end())
        {
            return -1;               // 未命中
        }
        Node* node = it->second;     // 拿到链表结点指针
        moveToFront(node);           // 命中即刷新为"最近使用"
        return node->value;          // 返回值
    }
 
    // put：key 已存在则更新值并刷新；不存在则新增，满了先淘汰
    void put(int key, int value)
    {
        auto it = _map.find(key);
        if (it != _map.end())
        {
            // 情况 A：key 已存在 -> 更新值 + 搬到头部
            Node* node = it->second;
            node->value = value;     // 原地改值（key 不变）
            moveToFront(node);       // 刷新新鲜度
            return;
        }
 
        // 情况 B：key 不存在 -> 新增
        if ((int)_map.size() >= _capacity)
        {
            // 缓存已满：淘汰表尾（最久未使用）
            Node* last = _tail->prev;            // 尾哨兵的前一个就是最久未使用
            _map.erase(last->key);               // 先从哈希表删登记
            removeNode(last);                    // 再从链表摘除
            delete last;                         // 释放内存（这是手写版多的一环）
        }
 
        // 新增结点，插入头部并在哈希表登记
        Node* node = new Node(key, value);
        _map[key] = node;            // 登记：key 指向这个新结点
        insertFront(node);           // 插到头部哨兵之后，记为最近使用
    }

#include <unordered_map>
#include <iostream>
using namespace std;
 
class LRUCache {
private:
    // 双向链表结点：存 key 与 value，并带前后指针
    struct Node {
        int key;
        int value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
 
    int capacity_;                 // 容量上限
    unordered_map<int, Node*> mp;  // 哈希表：key -> 链表结点指针
    Node* head;                    // 头哨兵，head->next 为最近使用
    Node* tail;                    // 尾哨兵，tail->prev 为最久未使用
 
    // 从链表中摘除结点（O(1)）
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
 
    // 把结点插到头哨兵后面（记为最近使用）
    void insertHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
 
    // 把已存在结点搬到头部：摘除 + 头插
    void moveToHead(Node* node) {
        removeNode(node);
        insertHead(node);
    }
 
public:
    // 构造：初始化容量，并让头尾哨兵互连为"空链表"
    LRUCache(int capacity) : capacity_(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
 
    ~LRUCache() {                       // 释放全部结点，避免内存泄漏
        Node* cur = head;
        while (cur) {
            Node* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
    }
 
    // 取 key 对应的值；命中则标记为最近使用；未命中返回 -1
    int get(int key) {
        // 用哈希表定位，O(1)
        if (mp.find(key) == mp.end())
            return -1;                  // 未命中
        Node* node = mp[key];
        moveToHead(node);               // 命中即刷新为最近使用
        return node->value;
    }
 
    // 写入；key 已存在则更新并刷新；否则新增，满了先淘汰最久未使用
    void put(int key, int value) {
        if (mp.count(key)) {            // 已存在：更新值 + 搬到头部
            Node* node = mp[key];
            node->value = value;
            moveToHead(node);
            return;
        }
        if ((int)mp.size() >= capacity_) {   // 已满：淘汰尾部结点
            Node* last = tail->prev;         // 最久未使用的结点
            mp.erase(last->key);             // 从哈希表删登记
            removeNode(last);                // 从链表摘除
            delete last;                     // 释放内存
        }
        Node* node = new Node(key, value);   // 新建结点
        mp[key] = node;                      // 哈希表登记
        insertHead(node);                    // 头插为最近使用
    }
};
 
// 自测用例：跑一遍就知道结果对不对
int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;   // 输出 1；此刻缓存里 2 变成最久
    cache.put(3, 3);                // 满了，淘汰 key 2
    cout << cache.get(2) << endl;   // 输出 -1（key 2 已被淘汰）
    cache.put(4, 4);                // 再满，淘汰 key 1（因 get(1) 很久没用）
    cout << cache.get(1) << endl;   // 输出 -1（key 1 已被淘汰）
    cout << cache.get(3) << endl;   // 输出 3
    cout << cache.get(4) << endl;   // 输出 4
    return 0;
}

#include <iostream>        // std::cout
#include <list>            // std::list 双向链表
#include <unordered_map>   // std::unordered_map 哈希表
#include <utility>         // std::pair / std::make_pair
using namespace std;
 
class LRUCache
{
public:
    LRUCache(int capacity)
        : _capacity(capacity)     // 记住容量上限
    {}
 
    // get：命中则刷新为最近使用并返回值；未命中返回 -1
    int get(int key)
    {
        auto hashIt = _map.find(key);      // 哈希表定位
        if (hashIt == _map.end())
            return -1;                     // 未命中
 
        auto listIt = hashIt->second;      // 拿到链表迭代器（桥接）
        pair<int, int> kv = *listIt;       // 拷贝出数据
        _list.erase(listIt);               // 原位置删除
        _list.push_front(kv);              // 头插为最近使用
        _map[key] = _list.begin();         // 重新登记迭代器（关键，勿漏）
        return kv.second;
    }
 
    // put：key 在则更新并刷新；不在则新增，满了先淘汰表尾
    void put(int key, int value)
    {
        auto hashIt = _map.find(key);
        if (hashIt != _map.end())
        {
            // 已存在：只更新 value，并搬到头部
            auto listIt = hashIt->second;
            pair<int, int> kv = *listIt;
            kv.second = value;
            _list.erase(listIt);
            _list.push_front(kv);
            _map[key] = _list.begin();
            return;
        }
 
        // 已满：先淘汰表尾（最久未使用），并同步删哈希表登记
        if ((int)_list.size() >= _capacity)
        {
            _map.erase(_list.back().first); // 删哈希表登记
            _list.pop_back();               // 删链表表尾
        }
 
        // 新增：头插 + 登记
        _list.push_front(make_pair(key, value));
        _map[key] = _list.begin();
    }
 
private:
    list<pair<int, int>> _list;                            // 链表：表头最近、表尾最久
    int _capacity;                                         // 容量
    unordered_map<int, list<pair<int, int>>::iterator> _map; // key -> 链表迭代器
};
 
int main()
{
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << "get(1) = " << cache.get(1) << endl;   // 1
    cache.put(3, 3);                               // 淘汰 2
    cout << "get(2) = " << cache.get(2) << endl;   // -1
    cache.put(4, 4);                               // 淘汰 1
    cout << "get(1) = " << cache.get(1) << endl;   // -1
    cout << "get(3) = " << cache.get(3) << endl;   // 3
    cout << "get(4) = " << cache.get(4) << endl;   // 4
    return 0;
}

#include <iostream>        // std::cout
#include <unordered_map>   // std::unordered_map
using namespace std;
 
class LRUCache
{
private:
    // 双向链表结点
    struct Node
    {
        int key;
        int value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
 
    int _capacity;
    unordered_map<int, Node*> _map;  // key -> 链表结点指针
    Node* _head;                     // 头哨兵：head->next 是最近使用
    Node* _tail;                     // 尾哨兵：tail->prev 是最久未使用
 
    // 摘除一个结点（O(1)）
    void removeNode(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
 
    // 头插（记为最近使用）
    void insertFront(Node* node)
    {
        node->next = _head->next;
        node->prev = _head;
        _head->next->prev = node;
        _head->next = node;
    }
 
    // 已存在结点搬到头部
    void moveToFront(Node* node)
    {
        removeNode(node);
        insertFront(node);
    }
 
public:
    LRUCache(int capacity)
        : _capacity(capacity)
        , _head(new Node(0, 0))
        , _tail(new Node(0, 0))
    {
        _head->next = _tail;   // 空链表初始互连
        _tail->prev = _head;
    }
 
    ~LRUCache()
    {
        Node* cur = _head;
        while (cur)
        {
            Node* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
    }
 
    int get(int key)
    {
        auto it = _map.find(key);
        if (it == _map.end())
            return -1;                 // 未命中
        Node* node = it->second;
        moveToFront(node);             // 命中刷新
        return node->value;
    }
 
    void put(int key, int value)
    {
        auto it = _map.find(key);
        if (it != _map.end())
        {
            Node* node = it->second;
            node->value = value;       // 更新值
            moveToFront(node);         // 搬到头部
            return;
        }
        if ((int)_map.size() >= _capacity)
        {
            Node* last = _tail->prev;  // 最久未使用
            _map.erase(last->key);     // 删哈希表
            removeNode(last);          // 拆链
            delete last;               // 释放
        }
        Node* node = new Node(key, value);
        _map[key] = node;              // 登记
        insertFront(node);             // 头插
    }
};
 
int main()
{
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << "get(1) = " << cache.get(1) << endl;   // 1
    cache.put(3, 3);                               // 淘汰 2
    cout << "get(2) = " << cache.get(2) << endl;   // -1
    cache.put(4, 4);                               // 淘汰 1
    cout << "get(1) = " << cache.get(1) << endl;   // -1
    cout << "get(3) = " << cache.get(3) << endl;   // 3
    cout << "get(4) = " << cache.get(4) << endl;   // 4
    return 0;
}