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->next->prev = node;
head->next = node;
node->prev = head;
}

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

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

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

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

ListNode* removeTail() {
    ListNode* node = tail->prev;
    removeNode(node);
    return node;
}
public:
LRUCache(int cap) : capacity(cap), size(0) {
head = new ListNode(0, 0);
tail = new ListNode(0, 0);
head->next = tail;
tail->prev = head;
}
~LRUCache() {
    while (head) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

int get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) return -1;
    ListNode* node = it->second;
    moveToHead(node);
    return node->value;
}

void put(int key, int value) {
    auto it = cache.find(key);
    if (it != cache.end()) {
        ListNode* node = it->second;
        node->value = value;
        moveToHead(node);
    } else {
        ListNode* newNode = new ListNode(key, value);
        cache[key] = newNode;
        addToHead(newNode);
        ++size;
        if (size > capacity) {
            ListNode* removed = removeTail();
            cache.erase(removed->key);
            delete removed;
            --size;
        }
    }
}
};