实现 LRU 缓存

描述

LRU 缓存机制

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

细节

  • 排出节点时没有把 tail 的 pre 置为排出点的 pre
  • 设计的 Node 节点只有 val 没有保存 key
  • 删除 map 中的键值对时删错
  • unordered_map 原地构造插入的方法为 .emplace(key, value)；
  • head, tail 成员声明时没有初始化

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class LRUCache {
private:
    class Node{
        public: // 注意是 public，或者改成 struct
            int key; int value;
            Node* pre; Node* next;
            Node(int _key = 0, int _value = 0, Node* _pre = nullptr, Node* _next = nullptr) : value(_value), key(_key), pre(_pre), next(_next) {}
    };
    unordered_map<int, Node*> map; // 快速查找
    int capacity; // 缓存的最大容量
    int size; // 当前缓存大小
    // 双链表的头尾，统一操作（记得初始化）
    Node* head = new Node();
    Node* tail = new Node();
    // 下面两个指针用于保存要调整到最前面的节点的前后节点
    Node* pre;
    Node* next;
    unordered_map<int, Node*>::iterator iter; // 保存每次根据 key 找到的 value 的迭代器

public:
    LRUCache(int _capacity) {
        capacity = _capacity; size = 0;
        head->next = tail; tail->pre = head;
    }

    int get(int key) {
        iter = map.find(key);
        if(iter != map.end()){
            adjust(iter->second);
            return iter->second->value;
        }else return -1;
    }

    void put(int key, int value) {
        int index = get(key);
        if(index == -1){ // 不存在
            Node* temp = new Node(key, value);
            if(size == capacity){ // 容量不够
                Node* end = tail->pre;
                end->pre->next = tail;
                tail->pre = end->pre;
                map.erase(end->key); // 注意这里擦去的是 end->key 而不是 key
                delete end; // 注意这句一定要在擦去 key 之后，否则就是引用悬空指针了(其实不 delete 也能通过所有测试用例)
                --size;
            }
            temp->next = head->next;
            head->next->pre = temp;
            temp->pre = head;
            head->next = temp;
            ++size;
            map.emplace(key, temp);
        }else{ // 存在
            iter->second->value = value;
            adjust(iter->second);
        }
    }

    void adjust(Node* item){
        pre = item->pre;
        next = item->next;
        pre->next = next;
        next->pre = pre;

        item->next = head->next;
        head->next->pre = item;
        item->pre = head;
        head->next = item;
    }

};

参考