LRU算法c++实现

LRU算法（最近最少使用算法）是一种用于缓存淘汰的算法。其原理是根据数据的访问时间来确定是否将其从缓存中删除。当缓存达到最大容量时，如果要插入新数据，则需要将最近最少使用的数据删除，以腾出空间。

以下是C++实现LRU算法的基本思路：

1. 使用一个双向链表来维护缓存的数据。
2. 使用一个哈希表来快速查找数据是否在缓存中。
3. 当一个数据被访问时，将其移动到链表头部。
4. 当需要插入新数据时，先检查缓存是否已满，如果已满，则删除链表尾部的数据，并将新数据插入到链表头部。
5. 当需要删除数据时，直接从链表中删除即可。

以下是C++代码示例：

#include <iostream>
#include <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;
    Node* head;
    Node* tail;

    void addToHead(Node* node) {
        node->prev = nullptr;
        node->next = head;
        if (head) {
            head->prev = node;
        } else {
            tail = node;
        }
        head = node;
    }

    void removeNode(Node* node) {
        if (node == head) {
            head = node->next;
        } else if (node == tail) {
            tail = node->prev;
        } else {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
    }

public:
    LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}

    int get(int key) {
        if (map.find(key) != map.end()) {
            Node* node = map[key];
            removeNode(node);
            addToHead(node);
            return node->value;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            Node* node = map[key];
            node->value = value;
            removeNode(node);
            addToHead(node);
        } else {
            Node* newNode = new Node(key, value);
            if (map.size() == capacity) {
                map.erase(tail->key);
                removeNode(tail);
                delete tail;
            }
            map[key] = newNode;
            addToHead(newNode);
        }
    }
};

int main() {
    LRUCache cache(2);

    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;   // 输出 1
    cache.put(3, 3);                // 删除 key 2
    cout << cache.get(2) << endl;   // 输出 -1
    cache.put(4, 4);                // 删除 key 1
    cout << cache.get(1) << endl;   // 输出 -1
    cout << cache.get(3) << endl;   // 输出 3
    cout << cache.get(4) << endl;   // 输出 4

    return 0;
}