手撕LRU-Go服务器开发

LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰策略。下面是一个手撕LRU缓存的示例实现：

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
private:
    int capacity;
    unordered_map<int, pair<int, list<int>::iterator>> cache;  // 存储键值对和对应迭代器
    list<int> lruList;  // 存储访问顺序

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

    int get(int key) {
        if (cache.find(key) == cache.end()) {  // 若key不存在于缓存中
            return -1;
        }

        // 将该元素移到链表头部表示最新访问
        lruList.erase(cache[key].second);
        lruList.push_front(key);
        cache[key].second = lruList.begin();

        return cache[key].first;  // 返回对应value值
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {  // 若key已存在于缓存中，则更新value，并将其移到链表头部表示最新访问
            lruList.erase(cache[key].second);
            lruList.push_front(key);
            cache[key] = make_pair(value, lruList.begin());
            return;
        }

        if (cache.size() == capacity) {  // 缓存已满，需要淘汰末尾的元素（即最久未使用）
            int lastKey = lruList.back();
            cache.erase(lastKey);
            lruList.pop_back();
        }

        // 插入新元素到链表头部表示最新访问
        lruList.push_front(key);
        cache[key] = make_pair(value, lruList.begin());
    }
};

int main() {
    LRUCache cache(2);  // 创建容量为2的LRU缓存

    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;  // 输出：1
    cache.put(3, 3); 
    cout << cache.get(2) << endl;  // 输出：-1，因为key=2被淘汰了
    cache.put(4, 4);
    cout << cache.get(1) << endl;  // 输出：-1，因为key=1被淘汰了
    cout << cache.get(3) << endl;  // 输出：3
    cout << cache.get(4) << endl;  // 输出：4

    return 0;
}

以上示例实现了一个LRU缓存，使用unordered_map来快速查找键值对，并用list来维护访问顺序。get操作会将访问的元素移到链表头部，put操作则会在缓存满时淘汰末尾的元素。

内容由零声教学AI助手提供，问题来源于学员提问