用c++实现LRU算法

以下是使用C++实现LRU算法的示例代码：

#include <unordered_map>
#include <list>

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

    int get(int key) {
        if (cache_map.count(key)) {
            auto iter = cache_map[key];
            cache_list.splice(cache_list.begin(), cache_list, iter);
            return iter->second;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (cache_map.count(key)) {
            auto iter = cache_map[key];
            iter->second = value;
            cache_list.splice(cache_list.begin(), cache_list, iter);
        } else {
            if (cache_map.size() == cap) {
                auto last = cache_list.back();
                cache_map.erase(last.first);
                cache_list.pop_back();
            }
            cache_list.emplace_front(key, value);
            cache_map[key] = cache_list.begin();
        }
    }

private:
    int cap;
    std::list<std::pair<int, int>> cache_list;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache_map;
};

LRUCache类中的cache_map属性是一个哈希表，用于快速查询某个key是否在缓存中。cache_list是一个双向链表，用于维护缓存中的元素顺序，最近使用的元素排在链表前面，最久未使用的元素排在链表后面。

在get方法中，如果key存在于哈希表中，就将对应的迭代器指向的节点移动到链表头部，并返回节点的value。如果key不存在于哈希表中，就返回-1。

在put方法中，如果key存在于哈希表中，就更新对应节点的value，并将其移动到链表头部。如果key不存在于哈希表中，就需要先判断缓存是否已满，如果已满，则需要先删除最近最少使用的节点（即尾节点），然后再添加新节点到链表头部。如果缓存未满，则直接将新节点添加到链表头部。在添加新节点时，需要同时在哈希表中记录节点在链表中的位置。