c++设计和实现LRU

LRU（Least Recently Used）是一种常用的页面置换算法，用于管理计算机内存系统或缓存中的数据。在C++中设计和实现LRU缓存，通常需要考虑以下几个方面：

1. 数据结构选择：为了实现高效的LRU缓存，通常需要结合使用哈希表（unordered_map）和双向链表（list）。哈希表用于O(1)时间复杂度的查找操作，而双向链表则用于维护数据项的使用顺序。

2. 功能实现：
- `get(key)`：如果缓存中存在key对应的值，则返回该值，并将该数据项移动到链表头部，表示最近使用；如果不存在，则返回-1。
- `put(key, value)`：首先检查key是否已存在于缓存中：
- 如果存在，更新对应的value，并将该数据项移动到链表头部。
- 如果不存在，先检查缓存是否已满：
- 如果已满，则删除链表尾部的数据项（即最久未使用的数据项）。
- 然后在链表头部插入新的数据项，并在哈希表中插入新的键值对。
- 使用双向链表实现数据项的插入和删除操作，需要维护链表的头尾指针。

3. 时间和空间复杂度：使用哈希表和双向链表组合实现的LRU缓存具有较低的时间复杂度O(1)进行插入、删除和查找操作。空间复杂度取决于缓存大小。

下面是一个简化的C++实现示例：

#include <unordered_map>
#include <list>
using namespace std;

class LRUCache {
private:
    int cap;
    list<pair<int, int>>缓存; // <key, value>
    unordered_map<int, list<pair<int, int>>::iterator>哈希表;

    void 移动到头部(int key) {
        auto iter = 哈希表[key];
        pair<int, int>键值对 = *iter;
        缓存.erase(iter);
        缓存.push_front(键值对);
        哈希表[key] = 缓存.begin();
    }

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (哈希表.find(key) == 哈希表.end()) {
            return -1;
        } else {
            移动到头部(key);
            return 哈希表[key]->second;
        }
    }

    void put(int key, int value) {
        if (哈希表.find(key) != 哈希表.end()) {
            移动到头部(key);
            哈希表[key]->second = value;
        } else {
            if (缓存.size() == cap) {
                auto last = 缓存.end();
                last--;
                哈希表.erase(last->first);
                缓存.pop_back();
            }
            缓存.push_front(make_pair(key, value));
            哈希表[key] = 缓存.begin();
        }
    }
};