LFU缓存通过频率节点与双向链表结构实现O(1)操作：每个键值对按频次分组为双向链表，频次链表按升序排列，辅以哈希表映射键到节点指针、minFreq记录最小有效频次，并在访问时迁移节点、超容时淘汰minFreq链表尾部节点。
一、构建频率节点与双向链表结构
LFU缓存需为每个键值对维护访问频次，并按频次分组组织成链表，同一频次的所有节点构成一个双向链表。频次链表本身也按频次升序排列，确保最低频次链表始终位于头部。该结构支持O(1)定位最低频次节点及同频次内最久未使用节点。
1、定义FreqNode结构体，包含key、value、freq三个字段，并配备prev和next指针指向同频次链表中的前后节点。
2、定义FreqList结构体，包含head、tail指针及size计数器，用于管理某一特定频次下的所有节点。
3、使用std::unordered_map
立即学习“C++免费学习笔记（深入）”；
4、维护minFreq变量，记录当前缓存中所有节点的最小有效频次，避免遍历查找。
二、哈希表映射键到频率节点指针
为实现O(1)的键查找与节点访问，需建立从key到FreqNode*的直接映射。该映射在get和put操作中被高频调用，是LFU维持常数时间性能的关键支撑层。
1、声明std::unordered_map
2、每次插入新节点时，同步将key与新分配的FreqNode*写入keyToNode。
3、每次删除节点时，先通过keyToNode获取目标FreqNode*，再执行链表解链与内存释放，并从keyToNode中erase该key。
4、在get操作中，直接通过keyToNode查得节点地址，无需遍历链表，避免了O(n)搜索开销。
三、访问频次更新与链表迁移逻辑
每次get或put命中已存在key时，需将其频次加1，并从原频次链表中移出，插入到新频次链表头部。该过程必须保证原链表与新链表的完整性，且minFreq在必要时递增。
1、从keyToNode中取出当前FreqNode* node。
2、获取其原始频次oldFreq = node->freq，将node->freq自增为newFreq = oldFreq + 1。
3、从oldFreq对应的FreqList中移除node：若该FreqList.size变为0且oldFreq == minFreq，则执行minFreq++。
4、将node插入newFreq对应的FreqList头部：若newFreq链表不存在，则新建并注册到freqToList映射中；插入操作必须更新head->next和原head的prev指针。
四、缓存容量超限时的淘汰策略执行
当put操作导致缓存节点总数超过capacity时，必须淘汰minFreq链表尾部的节点（即同频次中最久未使用的节点）。该策略严格遵循LFU定义，且依赖minFreq与尾部指针实现O(1)淘汰。
1、定位minFreq对应的FreqList* list = freqToList[minFreq]。
2、取list->tail->prev即为待淘汰节点evictNode（因tail为哨兵节点）。
3、从list中解链evictNode：更新其prev->next和next->prev指针，并调整list->size--。
4、从keyToNode中erase(evictNode->key)，释放evictNode内存；若list->size降为0，暂不删除FreqList对象，仅保留空链表供后续复用。
五、初始化与边界条件处理
构造LFUCache时需预置哨兵节点、初始化空映射及minFreq=0。所有链表操作均围绕哨兵节点展开，消除空指针判断分支，保障每步操作无条件执行。
1、为每个FreqList分配head和tail两个哨兵节点，初始化时令head->next = tail，tail->prev = head。
2、构造函数中设置capacity = cap，minFreq = 0，清空keyToNode与freqToList。
3、在put首次插入时，若capacity为0则直接返回，不执行任何节点分配或映射写入。
4、当缓存为空时，minFreq保持为0；首次插入后minFreq设为1，后续仅通过淘汰后链表为空触发递增。
