如何在C++中实现LRU缓存？

作者

在现代软件系统中，缓存机制常常用于提升访问速度，尤其是对于频繁读取但更新不太频繁的数据。LRU（Least Recently Used）缓存是一种常见的策略，它会在缓存满时淘汰最近最少使用的条目。下面将展示如何使用标准库中的容器和算法，结合双向链表与哈希表，实现一个高效的LRU缓存。

1. 设计思路

LRU 缓存需要支持两大操作：

  • get(key)：返回键对应的值，并把该键标记为最近使用。
  • put(key, value)：插入或更新键值对；若缓存已满，则淘汰最近最少使用的键。

实现关键点：

  • 双向链表：存储键的使用顺序，链表头是最近使用的，尾部是最久未使用的。
  • 哈希表：键到链表节点的映射，支持 O(1) 的查找。

2. 代码实现

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

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

    std::optional <Value> get(const Key& key) {
        auto it = cache_map_.find(key);
        if (it == cache_map_.end()) {
            return std::nullopt;      // 缓存未命中
        }
        // 把访问到的节点移动到链表前面
        cache_list_.splice(cache_list_.begin(), cache_list_, it->second);
        return it->second->second;     // 返回值
    }

    void put(const Key& key, const Value& value) {
        auto it = cache_map_.find(key);
        if (it != cache_map_.end()) {
            // 更新值并移动到链表前面
            it->second->second = value;
            cache_list_.splice(cache_list_.begin(), cache_list_, it->second);
            return;
        }

        // 若缓存已满，淘汰尾部元素
        if (cache_list_.size() == capacity_) {
            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:
    size_t capacity_;
    // 链表元素为 pair<key, value>
    std::list<std::pair<Key, Value>> cache_list_;
    // key -> iterator of list
    std::unordered_map<Key, typename std::list<std::pair<Key, Value>>::iterator> cache_map_;
};

3. 关键点解析

  1. splice 操作
    std::list::splice 可以在常数时间内把链表中的一个节点移动到指定位置，而不需要重新分配或复制。我们在 get 和已存在的 put 中都使用它把节点移到链表头。

  2. 缓存满时的淘汰
    cache_list_.back() 给出最久未使用的节点，直接 pop_back() 并从哈希表中移除对应键。

  3. 返回类型
    get 使用 std::optional 表示命中与否，避免返回特殊值导致歧义。

4. 使用示例

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

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

    std::cout << *cache.get(2) << std::endl;   // 输出 "two"

    cache.put(4, "four");  // 淘汰 key=1

    if (!cache.get(1).has_value()) {
        std::cout << "key 1 evicted" << std::endl;
    }

    return 0;
}

5. 性能分析

  • 时间复杂度
    get 与 put 的最坏时间复杂度均为 O(1)，因为哈希表查找、链表 splice 和 emplace_front 均为常数时间。

  • 空间复杂度
    需要 O(capacity) 的额外空间来存储链表节点和哈希表条目。

6. 进一步改进

  • 线程安全：可在 get/put 周围添加互斥锁，或使用读写锁提升并发性能。
  • 持久化：若缓存需要在程序重启后保持，可将链表和哈希表的状态写入磁盘或使用 LMDB、SQLite 等。
  • 自定义淘汰策略：在 put 时根据自定义规则（如权重）替换 splice 的位置。

通过以上实现，您可以在 C++ 项目中轻松嵌入高效的 LRU 缓存机制，显著提升数据访问的速度与响应效率。

发表评论