不能只用std::map或std::unordered_map实现lru，因其不维护访问时序，无法o(1)定位最久未用项；正确做法是结合std::unordered_map（o(1)查找）与std::list（o(1)移动/淘汰），map存储key→list迭代器，通过splice和及时更新迭代器实现高效lru。
为什么不能只用 std::map 或 std::unordered_map 实现 LRU？
因为 LRU 的核心是「访问时更新顺序 + 满时淘汰最久未用」，而 std::map 和 std::unordered_map 都不维护访问时间序。单纯靠 key-value 查找快，但没法 O(1) 找出「最久没被访问的那个 entry」。
常见错误是每次 get 都遍历整个容器重排，导致时间复杂度退化到 O(N)，完全失去 LRU 的实用价值。
- 真正可行的组合是：
std::unordered_map（负责 O(1) 查找） + 双向链表（负责 O(1) 移动和淘汰） - 标准库没有带移动语义的双向链表节点管理器，所以得自己维护
std::list或手写链表；用std::list更安全，但要注意迭代器失效问题 - 不能用
std::vector模拟链表——插入/删除不是 O(1)
如何用 std::list 和 std::unordered_map 协同管理节点？
关键在于 map 存的是 key → list iterator，而不是 key → value。这样每次 get 时，能用 iterator 直接在 list 中把对应节点移到 front（表示最新访问），同时 map 里仍能 O(1) 定位。
示例片段逻辑：
class LRUCache {
int capacity_;
std::list<:pair int>> cache_;
std::unordered_map<int std::list int>>::iterator> map_;
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key) {
auto it = map_.find(key);
if (it == map_.end()) return -1;
cache_.splice(cache_.begin(), cache_, it->second); // 移到头部
return it->second->second;
}
void put(int key, int value) {
auto it = map_.find(key);
if (it != map_.end()) {
it->second->second = value;
cache_.splice(cache_.begin(), cache_, it->second);
return;
}
if (cache_.size() >= capacity_) {
auto last = cache_.back();
map_.erase(last.first); // 注意：这里用 key 删除 map
cache_.pop_back();
}
cache_.emplace_front(key, value);
map_[key] = cache_.begin();
}
};</int></:pair>
-
cache_.splice(cache_.begin(), cache_, it->second)是高效移动的关键，避免拷贝 -
map_[key] = cache_.begin()必须在emplace_front后立即执行，否则cache_.begin()指向错误位置 - 删除末尾节点前，必须先从
map_中 erase 对应 key，否则残留 dangling iterator
std::list::iterator 在 put 重插后会失效吗？
不会——std::list 的 iterator 在插入、删除其他节点时**不会失效**，只有它指向的节点被显式删除时才失效。这是 std::list 被选作底层容器的根本原因。
但要注意两个陷阱：
- 调用
cache_.emplace_front(...)后，之前保存的所有 iterator（包括 map 中存的）仍然有效，但指向的位置不变；所以必须更新 map 中对应 key 的 iterator 值 - 如果用
cache_.push_front+std::make_pair，再取cache_.begin()赋值给 map，没问题；但若中间穿插了其他操作（比如先pop_back再push_front），要确保赋值时机正确 - 绝不能对同一节点多次调用
splice到相同位置——虽然不崩溃，但逻辑错乱
要不要考虑线程安全？
标准实现默认不考虑。如果多个线程并发调用 get/put，必须加锁，且粒度不能太粗——比如整个函数加 mutex 会严重拖慢吞吐。
- 简单做法：对整个
LRUCache实例加一个mutable std::mutex mtx_，所有 public 方法开头std::lock_guard<:mutex> lock(mtx_);</:mutex> - 更优但复杂：分离读写锁，或用
std::shared_mutex（C++17），get用 shared_lock，put用 unique_lock - 别尝试无锁——LRU 的链表重排 + map 更新天然需要原子协调，强行无锁极易出竞态，得不偿失
实际项目中，是否加锁取决于上层调用模型。很多场景下缓存本身由单一线程管理，或已在外围做了同步，这时候裸实现反而更轻量、更可控。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
