lru用std::list+std::unordered_map实现，通过链表维护访问时序（最新在头、淘汰尾部），map存key到链表迭代器的映射，确保get/put均为o(1)；lfu需按频次分桶，每桶内lru管理，辅以minfreq优化淘汰；不用std::map因其实现为红黑树，查找o(log n)，不满足缓存高频o(1)要求。
LRU 用 std::list + std::unordered_map 实现最简可靠版本
核心是维护「访问时序」：最新访问的放链表头，淘汰时删尾部。不能只靠 map 记 key-value，必须用双向链表快速移动节点位置。
-
std::list<:pair int>></:pair>存{key, value}，支持 O(1) 删除任意节点和 push_front -
std::unordered_map<int std::list int>>::iterator></int>快速定位 key 对应的链表迭代器 - 每次
get()：查 map → 找到则从 list 中 erase 原位置，再push_front()，更新 map 中迭代器 - 每次
put()：若 key 已存在，同上更新；否则检查容量，满则先pop_back()并删 map 中对应 key，再插入新节点
class LRUCache {
int cap;
std::list<std::pair<int, int>> cache;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (map.find(key) == map.end()) return -1;
auto it = map[key];
int val = it->second;
cache.erase(it);
cache.push_front({key, val});
map[key] = cache.begin();
return val;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
cache.erase(map[key]);
} else if (cache.size() >= cap) {
auto last = cache.back();
map.erase(last.first);
cache.pop_back();
}
cache.push_front({key, value});
map[key] = cache.begin();
}
};
LFU 需要频率分组 + 双向链表嵌套，std::unordered_map 套 std::list 是关键结构
LFU 淘汰最低频且最久未用的项，光记 frequency 不够 —— 同频次下还得有访问时序。所以得按 freq 分桶，每桶内用 LRU 方式管理（即链表），再用 map 索引每个 key 所在的桶和节点。
- 外层：
std::unordered_map<int std::list>></int>，key 是 frequency，value 是该频次下所有Node{key, value, freq}的链表 - 中间：
std::unordered_map<int std::pair>::iterator, int>></int>，记录 key →{所在链表迭代器, 当前 freq} - 还需一个
int minFreq，用于 O(1) 找到待淘汰桶（避免遍历所有 freq） -
get()：查 key → 得到 oldFreq；从 oldFreq 桶中删除节点；插入到oldFreq + 1桶头；若 oldFreq 桶空且等于minFreq，则minFreq++ -
put()：若 key 存在，同get()更新；否则新建 Node 插入 freq=1 桶，minFreq = 1；若超容，删minFreq桶尾节点
为什么不用 std::map 替代 std::unordered_map？性能差在哪
std::map 是红黑树，O(log n) 查找；而缓存操作要求 O(1) 定位，尤其在高并发或高频调用场景下，log n 会明显拖慢吞吐。实测百万次 get()，unordered_map 比 map 快 3–5 倍。
- 除非你需要按 key 排序（LFU/LRU 都不需要），否则无理由选
std::map -
unordered_map的哈希冲突在负载因子 .reserve(n) 避免 rehash - 注意自定义 key 类型需提供
hash和==，内置类型如int、string已内置
容易被忽略的边界：迭代器失效与 list::splice() 的正确用法
直接 erase() 再 push_front() 看似自然，但对 list 迭代器来说，erase 后原迭代器立即失效 —— 而 map 里还存着它，下次访问就 UB。正确做法是用 splice() 移动节点，不破坏迭代器有效性。
立即学习“C++免费学习笔记（深入）”；
- 错误写法：
cache.erase(it); cache.push_front(...); map[key] = cache.begin();→ it 已失效，但 map 未清，后续可能解引用野指针 - 正确写法（LRU）：
cache.splice(cache.begin(), cache, it); map[key] = cache.begin();→splice是移动，it仍有效 - LFU 中跨桶移动也必须用
splice，否则旧桶 erase 后，map 中保存的迭代器指向已销毁内存
minFreq 的维护和空桶清理最容易漏；哪怕只少一行 if (buckets[oldFreq].empty()) minFreq = std::min(minFreq, oldFreq + 1);，都会导致后续淘汰错对象。 
