C++实现LRU缓存的思路与代码示例

struct ListNode {
    int key, value;
    ListNode *prev, *next;
    ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

void removeNode(ListNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}
void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}

#include 
#include 
using namespace std;
class LRUCache {
private:
struct ListNode {
int key, value;
ListNode prev, next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map cache;
ListNode *head, *tail;

void removeNode(ListNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

void addToHead(ListNode* node) {
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

void moveToHead(ListNode* node) {
    removeNode(node);
    addToHead(node);
}

ListNode* popTail() {
    ListNode* last = tail->prev;
    removeNode(last);
    return last;
}
public:
LRUCache(int cap) {
capacity = cap;
head = new ListNode(0, 0);
tail = new ListNode(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
    if (cache.find(key) == cache.end()) return -1;
    ListNode* node = cache[key];
    moveToHead(node);
    return node->value;
}

void put(int key, int value) {
    if (cache.find(key) != cache.end()) {
        ListNode* node = cache[key];
        node->value = value;
        moveToHead(node);
    } else {
        ListNode* newNode = new ListNode(key, value);
        cache[key] = newNode;
        addToHead(newNode);

        if (cache.size() > capacity) {
            ListNode* removed = popTail();
            cache.erase(removed->key);
            delete removed;
        }
    }
}

~LRUCache() {
    for (auto& pair : cache) {
        delete pair.second;
    }
    delete head;
    delete tail;
}
};

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    cout << lru.get(1) << endl; // 输出 1
    lru.put(3, 3);               // 淘汰 key=2
    cout << lru.get(2) << endl; // 输出 -1
    return 0;
}