前言

实现一个LRU算法,感觉比较简单,开始吧。

正文

LRU算法的原理这里不再赘述,网上太多了,直接来看我们的代码。

首先看下结构体,我们先声明一个Node节点

我们这里用双向链表来组织。

成员变量

用unordered_map来存储k和对应的节点,latch要声明为mutable的才能让const函数来改变

然后就是我们cpp里面的实现,看下insert,如果这个value存在就刷新他到前面去,否则就插入一个新的节点到head后面。

victim用来删除最老的那个节点

Erase删除某个节点

最后pass过test

总结

lru还是很简单的,就是用一个双向链表来组织。