LRU算法用C++实现

LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存淘汰策略，当缓存空间不足时，会优先移除最近最长时间未使用的数据。在C++中，可以使用链表结构和哈希表结合来实现一个简单的LRU缓存。以下是基本步骤：

1. 创建两个容器：
- 一个双向链表，用于存储缓存的数据及其访问顺序。
- 一个哈希表（unordered_map），用于快速查找元素。

2. 定义一个`Node`结构体，包含数据`key`、值`value`以及双向链表的头指针和尾指针。

struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
};

3. 缓存类`LRUCache`，包括容量`capacity`和一个大小为`capacity`的双向链表头部和尾部：

class LRUCache {
private:
    size_t capacity;
    unordered_map<int, Node*> map;
    Node* head;
    Node* tail;

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

    // ...其他操作...
};

4. 添加数据到缓存和维护链表和哈希表的关系：
- `insert(key, value)`：如果键存在，更新其值并调整链表位置；如果满，删除尾部节点再插入新节点。
- `get(key)`：如果键不存在直接返回-1；如果存在但不在头位置，移动到头位置后再返回值。

5. 删除数据（移除尾部节点）：
- 当缓存满且有新的请求时，删除尾部节点，并从哈希表中移除。

6. 最后，实现必要的`delete`、`moveToHead`等辅助函数来完成整个流程。

注意，这只是一个简化的版本，实际实现可能还需要考虑并发控制（如读写锁）来保证线程安全。如果你想详细了解，可以查阅相关的博客文章或教程。