如何在 C++ 中实现一个高效的 LRU 缓存？

作者

实现一个 LRU（Least Recently Used）缓存，主要目标是保持最近使用的键值对在前，淘汰最久未使用的条目，并且在 O(1) 时间复杂度内完成访问、插入和删除操作。常见做法是将哈希表（std::unordered_map）与双向链表（std::list）结合使用。哈希表提供快速定位键对应的节点，链表则维护使用顺序。下面给出一个完整可编译的实现示例，并演示其使用方法。

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

template <typename Key, typename Value>
class LRUCache {
public:
    explicit LRUCache(size_t capacity) : capacity_(capacity) {}

    // 读取键对应的值，如果存在返回 true 并赋值给 value
    bool get(const Key& key, Value& value) {
        auto it = cacheMap_.find(key);
        if (it == cacheMap_.end()) {
            return false; // 缓存未命中
        }
        // 把访问的节点移到链表前端（最近使用）
        touch(it);
        value = it->second->second;
        return true;
    }

    // 写入或更新键值对
    void put(const Key& key, const Value& value) {
        auto it = cacheMap_.find(key);
        if (it != cacheMap_.end()) {
            // 更新已有条目
            it->second->second = value;
            touch(it);
            return;
        }

        // 新条目，先检查是否需要淘汰
        if (cacheMap_.size() == capacity_) {
            evict();
        }

        // 插入到链表前端
        cacheList_.emplace_front(key, value);
        cacheMap_[key] = cacheList_.begin();
    }

    void debugPrint() const {
        std::cout << "Cache state (MRU -> LRU):\n";
        for (const auto& kv : cacheList_) {
            std::cout << kv.first << ":" << kv.second << " ";
        }
        std::cout << "\n";
    }

private:
    using ListIt = typename std::list<std::pair<Key, Value>>::iterator;

    void touch(typename std::unordered_map<Key, ListIt>::iterator it) {
        // 将对应节点移动到链表前端
        cacheList_.splice(cacheList_.begin(), cacheList_, it->second);
        it->second = cacheList_.begin();
    }

    void evict() {
        // 淘汰链表尾部（最久未使用）
        auto last = cacheList_.end();
        --last;
        cacheMap_.erase(last->first);
        cacheList_.pop_back();
    }

    size_t capacity_;
    std::list<std::pair<Key, Value>> cacheList_;              // 双向链表
    std::unordered_map<Key, ListIt> cacheMap_;                // 哈希表映射键 -> 链表迭代器
};

int main() {
    LRUCache<std::string, int> cache(3);

    cache.put("one", 1);
    cache.put("two", 2);
    cache.put("three", 3);
    cache.debugPrint(); // one:1 two:2 three:3

    int value;
    cache.get("one", value); // 访问 one，变成 MRU
    cache.debugPrint();      // one:1 three:3 two:2

    cache.put("four", 4);     // 缓存满，淘汰 two
    cache.debugPrint();      // four:4 one:1 three:3

    if (!cache.get("two", value)) {
        std::cout << "\"two\" not found in cache.\n";
    }

    cache.put("five", 5);     // 再次淘汰 three
    cache.debugPrint();      // five:5 four:4 one:1

    return 0;
}

关键点解析

  1. 双向链表 (std::list)

    • 维持键值对的使用顺序。链表头部代表最近使用（MRU），尾部代表最久未使用（LRU）。
    • splice 操作可以在常数时间内把任意节点移动到链表前端。

  2. 哈希表 (std::unordered_map)

    • 将键映射到链表中的迭代器，能够在 O(1) 时间内定位对应节点。
    • 结合链表的 splice 能够实现快速更新。

  3. 容量控制

    • 当插入新条目且缓存已满时，调用 evict()，移除链表尾部元素并更新哈希表。

  4. 通用模板化

    • 通过 template，该实现可以用于任何键和值类型，只要键支持哈希（需要 `std::hash `）并且可比较。

性能特点

  • 时间复杂度：
    • get、put 均为 O(1)。
    • evict 也是 O(1)，因为只需弹出尾部元素。
  • 空间复杂度：O(capacity)，仅存储最近 capacity 个条目。

进一步优化

  • 若对线程安全有需求，可在外层使用互斥锁，或者使用 std::shared_mutex 实现读写分离。
  • 对于大容量缓存，链表占用的内存相对较高，可以改用 std::vector 并维护一个双向链表的数组实现（如“LRU Cache with Linked Hash Map”）。
  • 若需要对缓存条目做自定义过期策略，可在链表节点中存放时间戳，并定期扫描清理。

以上示例展示了一个完整、易于理解且高效的 LRU 缓存实现，适合在 C++ 项目中直接使用或作为学习参考。

发表评论