LRU,顾名思义:最近最少使用的删除缓存。
基本思路:
用链表来存,每次查询都把查到的节点放到头部。
题目限定O(1),等于说要求用哈希表来做。
那就简单了:
unordered_map<key, data *> 存放key对应的数据指针;
链表这边虚拟出头节点和尾节点保证操作一致即可,剩下的get和put都是增删改查业务逻辑:
get:map到data->val返回即可
put:
有:直接修改data->val,而后move2head
没有:先insert2head,size如果超出就deltail