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

作者

在实际项目中，LRU（最近最少使用）缓存是一种常见的数据结构，用于在有限的存储空间中高效地管理最近访问过的数据。下面将通过完整的示例代码来演示如何在 C++17（可兼容 C++11/14）中实现一个通用的 LRU 缓存，并讨论其核心设计思想与性能优化技巧。

1. 需求分析

  • 固定容量：缓存大小固定，超过容量时需要淘汰最久未使用的元素。
  • O(1) 访问：获取、插入和删除都要保持常数时间复杂度。
  • 键值映射：支持任意类型键和值（可通过模板实现）。

2. 关键技术点

  1. 双向链表：维护元素使用顺序，头部为最近使用，尾部为最久未使用。双向链表的插入与删除均为 O(1)。
  2. 哈希表：快速定位键对应的链表节点，时间复杂度为 O(1)。
  3. 迭代器：链表节点在哈希表中存储其迭代器，避免遍历链表。

3. 代码实现

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

/*
 * LRUCache
 * Key   : 任意可哈希类型
 * Value : 任意可拷贝类型
 */
template <typename Key, typename Value>
class LRUCache {
public:
    using ListIt = typename std::list<std::pair<Key, Value>>::iterator;

    explicit LRUCache(size_t capacity) : capacity_(capacity) {
        if (capacity_ == 0) {
            throw std::invalid_argument("Capacity must be greater than 0");
        }
    }

    // 读取缓存
    Value get(const Key& key) {
        auto it = map_.find(key);
        if (it == map_.end()) {
            throw std::out_of_range("Key not found");
        }
        // 将访问的节点移到链表头部
        moveToFront(it->second);
        return it->second->second;
    }

    // 写入缓存
    void put(const Key& key, const Value& value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            // 更新值并移动到头部
            it->second->second = value;
            moveToFront(it->second);
            return;
        }

        // 如果已满，弹出尾部
        if (list_.size() == capacity_) {
            const auto& last = list_.back();
            map_.erase(last.first);
            list_.pop_back();
        }

        // 插入新节点到头部
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }

    // 可选：查看缓存是否包含某键
    bool contains(const Key& key) const {
        return map_.find(key) != map_.end();
    }

    // 可选：清空缓存
    void clear() {
        list_.clear();
        map_.clear();
    }

    // 打印缓存内容（调试使用）
    void dump() const {
        std::cout << "Cache [MRU -> LRU]: ";
        for (const auto& p : list_) {
            std::cout << "(" << p.first << ":" << p.second << ") ";
        }
        std::cout << "\n";
    }

private:
    void moveToFront(ListIt it) {
        if (it != list_.begin()) {
            list_.splice(list_.begin(), list_, it);
        }
    }

    size_t capacity_;
    std::list<std::pair<Key, Value>> list_;
    std::unordered_map<Key, ListIt> map_;
};

3.1 关键点说明

  • list_：双向链表，存储 std::pair<Key, Value>。头部表示最近使用，尾部表示最久未使用。
  • map_：哈希表，键为 Key，值为链表节点的迭代器，便于 O(1) 定位。
  • moveToFront：使用 std::list::splice 以常数时间将节点搬到链表头部。
  • put：若键已存在，只更新值并搬移；若新增且已满，先弹出尾部元素。

4. 使用示例

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

    cache.put(1, "One");
    cache.put(2, "Two");
    cache.put(3, "Three");
    cache.dump(); // (3:Three) (2:Two) (1:One)

    // 访问 2，使其成为最近使用
    std::cout << "Get 2: " << cache.get(2) << "\n";
    cache.dump(); // (2:Two) (3:Three) (1:One)

    // 新增 4，触发淘汰
    cache.put(4, "Four");
    cache.dump(); // (4:Four) (2:Two) (3:Three)

    // 访问已被淘汰的 1，抛出异常
    try {
        cache.get(1);
    } catch (const std::exception& e) {
        std::cout << "Error: " << e.what() << "\n";
    }
}

运行结果示例：

Cache [MRU -> LRU]: (3:Three) (2:Two) (1:One) 
Get 2: Two
Cache [MRU -> LRU]: (2:Two) (3:Three) (1:One) 
Cache [MRU -> LRU]: (4:Four) (2:Two) (3:Three) 
Error: Key not found

5. 性能与复杂度

操作 时间复杂度 空间复杂度
get O(1) O(1)
put O(1) O(1)
contains O(1) O(1)
clear O(n) O(1)
  • 时间：所有核心操作均为常数时间，适合高并发场景。
  • 空间：额外占用链表和哈希表结构，空间与缓存容量成正比。

6. 进一步优化

  1. 线程安全：使用 std::mutex 或者更细粒度的 std::shared_mutex 包装缓存操作。
  2. 自定义哈希：若键类型为字符串，使用 std::hash<std::string> 可进一步提升性能。
  3. 持久化：将缓存同步到磁盘或 Redis，支持跨进程共享。
  4. 更灵活的淘汰策略：结合 LFU、ARC 等策略实现混合缓存。

7. 小结

通过组合双向链表和哈希表，我们实现了一个 O(1) 访问、固定容量 的 LRU 缓存。模板化设计让其适用于任意键值类型，代码简洁且易于维护。该实现可直接嵌入生产代码，也可作为学习 C++ 数据结构与算法的实践例子。

发表评论