lru算法c++

以下是C++实现的LRU算法代码：

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

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) {
            return -1;
        }
        // 把当前访问的元素移到链表头部，并更新unordered_map中该元素的地址
        cacheList.splice(cacheList.begin(), cacheList, cache[key]);
        cache[key] = cacheList.begin();

        return cache[key]->second;
    }
    
    void put(int key, int value) {
        if (cache.count(key) == 0) {
            if (cacheList.size() == cap) {
                // 删除链表最后一个元素
                auto last = cacheList.end();
                last--;
                cache.erase(last->first);
                cacheList.erase(last);
            }
            // 插入新元素到链表头部，并在unordered_map中记录该元素的地址
            cacheList.push_front(make_pair(key, value));
            cache[key] = cacheList.begin();
        }
        else {
            // 把当前访问的元素移到链表头部，并更新unordered_map中该元素的地址
            cacheList.splice(cacheList.begin(), cacheList, cache[key]);
            cache[key] = cacheList.begin();
            // 更新元素的值
            cache[key]->second = value;
        }
    }

private:
    int cap;
    // cacheList的元素是pair<key, value>，其中key和unordered_map中的key相同，
    // value是实际存储的value值。链表按照访问时间从新到旧排序
    list<pair<int, int>> cacheList;
    // unordered_map的key是LRU缓存的key，value是LRU缓存中key对应节点在cacheList中的地址
    unordered_map<int, list<pair<int, int>>::iterator> cache;
};

int main() {
    LRUCache lruCache(2);

    lruCache.put(1, 1);
    lruCache.put(2, 2);
    cout << lruCache.get(1) << endl; // 1
    lruCache.put(3, 3);
    cout << lruCache.get(2) << endl; // -1
    lruCache.put(4, 4);
    cout << lruCache.get(1) << endl; // -1
    cout << lruCache.get(3) << endl; // 3
    cout << lruCache.get(4) << endl; // 4

    return 0;
}

LRU算法的核心思想是，缓存一定的数据，并在缓存满时，删除最近最少访问的数据，为新的数据留出空间。以上代码实现了一个LRU缓存类，使用了双向链表和哈希表。其中双向链表按照访问时间从新到旧排序，哈希表记录了每个key对应的节点在链表中的地址。在get操作中，如果请求的key不存在于哈希表中，则返回-1；如果存在于哈希表中，则把对应的节点移到链表头部，并返回节点的value值。在put操作中，如果请求的key不存在于哈希表中，则把新元素插入到链表头部，并删除链表最后一个元素；如果存在于哈希表中，则把对应的节点移到链表头部，并更新节点的value值。