lru-k区别于标准lru在于记录每个键最近k次访问时间戳，淘汰时依据第k次访问时间排序（越早越先淘汰），从而缓解偶发热点导致的缓存污染；k=1时退化为标准lru，实际常用k=2或3。
LRU-K和标准LRU的区别在哪？
LRU-K不是简单地记录“最近一次访问时间”，而是记录每个键的**最近K次访问时间戳**，淘汰时按第K次访问的时间排序——越早的第K次访问，优先被淘汰。这能缓解“偶发热点”误判问题（比如某个key被扫了一次就冷了，但标准LRU会把它保很久）。实际中K通常取2或3，K=1退化为标准LRU。
关键点：不能只存一个last_access，得维护一个长度≤K的有序时间戳列表；每次get要更新这个列表，并保证它始终按时间倒序排列（最新在前）。
用C++11实现核心数据结构要注意什么？
推荐用std::unordered_map存key→std::vector<:chrono::steady_clock::time_point></:chrono::steady_clock::time_point>，但vector频繁push_back+sort太重。更高效做法是：每次get时，用std::upper_bound找插入位置，然后用insert维持倒序；超过K个就pop_back（最老的那个）。
- 别用
std::map替代std::unordered_map——查找O(1)比O(log n)重要得多 - 时间戳必须用
std::chrono::steady_clock，避免系统时间回拨导致排序错乱 - 淘汰逻辑里，遍历所有entry取第K个时间戳时，用
std::min_element配合lambda，别手写循环
淘汰策略怎么写才不拖慢get/put？
LRU-K的淘汰不能在每次put时全量扫描——那是O(N×K)。正确做法是：只在缓存满时触发一次淘汰，且用std::priority_queue预热。构造一个以“第K个时间戳”为key的小顶堆，每个节点存key和对应第K个时间戳（如果不足K次，用time_point::min()代替）。
示例片段：
using Timestamp = std::chrono::steady_clock::time_point;
struct EvictNode {
std::string key;
Timestamp kth_access;
bool operator>(const EvictNode& rhs) const { return kth_access > rhs.kth_access; }
};
std::priority_queue<evictnode std::vector>, std::greater<evictnode>> pq;
</evictnode></evictnode>
每次put后，若size超限，pop堆顶key并从map中erase。注意：堆里节点可能过期（对应entry已被更新），所以pop后要检查cache_map.count(popped.key)是否仍存在。
为什么LRU-K在多线程下容易出错？
多个线程同时对同一个key调用get，会并发修改它的vector——这不是std::vector的线程安全操作。常见错误是只给整个cache加一把锁，导致所有key串行访问，吞吐暴跌。
可行解法：
- 每个key配一个
std::shared_mutex（C++17），读get用shared_lock，写update vector用unique_lock - 或者改用分段锁：把hash值对N取模，N个
std::shared_mutex分散保护不同桶 - 绝对不要在get里做
erase+reinsert这种两步操作——中间可能被其他线程删掉
真正难的不是算法本身，而是让第K次访问时间戳在并发下始终可比较、不丢失。多数人卡在这儿，而不是逻辑写不对。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
