列出包 `MoveToFront` 不适合我

Question

Go 的新手并在 Go 中构建一个简单的 LRU 缓存以习惯语法和 Go 开发。

MoveToFront 列表方法有问题，它在 MoveToFront 正文中的以下检查中失败

if e.list != l || l.root.next == e 

当我从缓存中检索它时，我想将元素 (e) 移动到列表的前面，就像这样

if elem, ok := lc.entries[k]; ok {
    lc.list.MoveToFront(elem) // needs fixing
    return elem
}
return nil

出现问题的代码可以看这里第32行

https://github.com/hajjboy95/golrucache/blob/master/lru_cache/lrucache.go#L32

Answer 1

对我来说似乎有两个问题。首先，这不是 List 数据类型的用途:lc.list.PushFront() 将创建 List.Element 并返回指向它的指针。这不是致命的，但至少有点烦人——调用者在使用 Get 时必须深入挖掘返回的 List.Element，而不是仅仅获取值.

与此同时，您看到的失败大概是因为当 LRU 列表空间不足时，您在 Put 中删除了元素，但没有从相应的映射中删除它们。因此，稍后对刚刚删除的键的 Put 将尝试在适当的位置重新使用该元素，即使该元素已从列表中删除也是如此。要解决此问题，您需要同时持有键和值。 (在我的简单实验中，我没有看到任何失败，但问题变得很清楚。)

我稍微重组了代码并将其变成了 working example on the Go Playground .我不对适用性等做出任何 promise 。