lru c++

### LRU Cache 实现的背景与原理 LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，其核心思想是记录元素的访问顺序，并在缓存达到容量上限时自动替换最不常用的元素[^1]。这种机制特别适合于需要快速查找复杂计算结果，同时避免内存过载的场景。 ### C++ 中实现 LRU 缓存的方式 C++ 提供了多种数据结构可以用来实现 LRU 缓存。一个典型的实现方式是结合 `std::unordered_map` 和 `std::list` 来完成。以下是实现的核心思路： - 使用 `std::unordered_map` 存储键值对，以便能够以 O(1) 的时间复杂度进行查找。 - 使用 `std::list` 保存键值对的使用顺序，最近使用的放在列表头部，最久未使用的放在列表尾部。 - 当插入新元素或访问现有元素时，将该元素移动到列表头部。 - 当缓存容量已满时，删除列表尾部的元素。 以下是一个完整的 C++ 实现示例： ```cpp #include <iostream> #include <unordered_map> #include <list> #include <stdexcept> template<typename Key, typename Value> class LRUCache { private: size_t capacity; std::list<std::pair<Key, Value>> cache_list; std::unordered_map<Key, typename std::list<std::pair<Key, Value>>::iterator> cache_map; public: LRUCache(size_t cap) : capacity(cap) {} Value get(const Key& key) { if (cache_map.find(key) == cache_map.end()) { throw std::out_of_range("Key not found"); } // Move the accessed element to the front auto it = cache_map[key]; cache_list.splice(cache_list.begin(), cache_list, it); return it->second; } void put(const Key& key, const Value& value) { if (cache_map.find(key) != cache_map.end()) { // Update the value and move the element to the front auto it = cache_map[key]; it->second = value; cache_list.splice(cache_list.begin(), cache_list, it); } else { if (cache_list.size() >= capacity) { // Remove the least recently used element from both list and map Key lru_key = cache_list.back().first; cache_list.pop_back(); cache_map.erase(lru_key); } // Insert the new element at the front cache_list.emplace_front(key, value); cache_map[key] = cache_list.begin(); } } }; int main() { LRUCache<int, int> cache(2); // Create an LRU cache with capacity 2 cache.put(1, 10); cache.put(2, 20); std::cout << "Get key 1: " << cache.get(1) << std::endl; // Should return 10 cache.put(3, 30); // Evicts key 2 try { std::cout << "Get key 2: " << cache.get(2) << std::endl; // Should throw exception } catch (const std::out_of_range& e) { std::cout << "Key 2 not found" << std::endl; } cache.put(4, 40); // Evicts key 1 try { std::cout << "Get key 1: " << cache.get(1) << std::endl; // Should throw exception } catch (const std::out_of_range& e) { std::cout << "Key 1 not found" << std::endl; } std::cout << "Get key 4: " << cache.get(4) << std::endl; // Should return 40 return 0; } ``` 上述代码展示了如何通过模板类实现一个通用的 LRU 缓存。用户可以通过指定键和值的类型来创建不同类型的缓存实例。此外，还可以选择使用 `std::map` 或 `std::unordered_map` 来存储键值对[^2]。 ### 性能与适用场景 此实现具有以下特点： - 查找、插入和删除操作的时间复杂度均为 O(1)，因为 `std::unordered_map` 提供了常数时间的查找，而 `std::list` 提供了高效的元素移动。 - 它适用于需要频繁访问少量数据并希望减少内存占用的场景[^1]。