LRU 缓存 基于哈希表 C++

LRU 缓存基于哈希表的实现可以使用 STL 中的 `std::unordered_map`，这个容器提供了 O(1) 的查找和插入操作，非常适合用于实现缓存。下面是一个基于哈希表实现的 LRU 缓存的 C++ 代码：

#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto iter = cache_.find(key);
        if (iter == cache_.end()) {
            return -1;
        } else {
            auto value = iter->second->second;
            cache_list_.splice(cache_list_.begin(), cache_list_, iter->second);
            iter->second = cache_list_.begin();
            return value;
        }
    }

    void put(int key, int value) {
        auto iter = cache_.find(key);
        if (iter == cache_.end()) {
            if (cache_.size() == capacity_) {
                int key_to_remove = cache_list_.back().first;
                cache_.erase(key_to_remove);
                cache_list_.pop_back();
            }
            cache_list_.push_front({key, value});
            cache_[key] = cache_list_.begin();
        } else {
            iter->second->second = value;
            cache_list_.splice(cache_list_.begin(), cache_list_, iter->second);
            iter->second = cache_list_.begin();
        }
    }

private:
    int capacity_;
    std::list<std::pair<int, int>> cache_list_;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache_;
};

在这个实现中，我们使用了一个双向链表 `cache_list_` 来保存缓存中的数据，并使用一个哈希表 `cache_` 来提高查找效率。在 `get` 操作中，我们先在哈希表中查找目标数据，如果不存在则返回 -1，否则将目标数据移到链表头部并返回其值。在 `put` 操作中，如果缓存中不存在目标数据则创建一个新的节点并将其添加到链表头部，如果缓存已满则删除链表尾部的节点。如果缓存中已存在目标数据则将其值更新并将其移动到链表头部。

需要注意的是，在 `get` 操作中，我们需要使用 `splice` 操作将目标节点移到链表头部，并更新哈希表中对应节点的指针。在 `put` 操作中，我们需要先判断缓存是否已满，如果已满则删除链表尾部的节点，并在哈希表中删除对应的键值对。然后我们将新节点添加到链表头部，并在哈希表中创建对应的键值对。

另外，由于我们使用了 STL 中的 `std::list`，所以我们可以直接使用 `push_front` 和 `pop_back` 操作来添加和删除链表节点，非常方便。