LRUCache 编写中容易遇到的问题#

本笔记记录我在实现 LRUCache 过程中常见的坑，结合之前几个版本中出现过的错误整理而成。

1. 节点与哈希表的对应关系#

节点没有保存 key：淘汰时无法从 map_ 删除正确的条目，导致 map_ 留下悬空指针。
节点 key 未赋值：即使有 key_ 字段，如果构造时忘记赋值，map_.erase(last->key_) 会删除错误条目或删除失败。

2. put() 逻辑错误#

已存在 key 直接 return：没有更新值，也没有更新最近使用顺序。
已存在 key 又创建新节点：旧节点留在链表里，新节点覆盖 map_[key]，会造成链表中“孤儿节点”与内存泄漏。
新节点没插入链表：创建了节点但插入的却是错误指针，导致链表结构被破坏。

3. 淘汰逻辑错误#

删除错误的哈希表项：在淘汰时用 map_.erase(target)，但 target 不是被淘汰节点对应的迭代器。
容量为 0 的处理：若不禁止 capacity_ == 0，可能会删除哨兵节点，破坏链表结构。

4. LRU 顺序维护不一致#

get 与 put 采用不同方向：get() 把节点移到头部，但 put() 插到尾部，造成“最近使用”的语义混乱，淘汰策略错误。

5. 析构与内存安全问题#

析构函数中使用已释放的指针：删除 head_ 后仍用 head_->next_ 继续遍历，属于未定义行为。
类可拷贝导致双重释放：有裸指针但未禁用拷贝/赋值，会在拷贝对象销毁时双重释放。

6. 计数与容量维护#

nums_ 未同步更新：淘汰时如果不减少计数，nums_ 会一直等于 capacity_，影响后续逻辑或可读性。

7. 其他可维护性问题#

命名歧义：get(K value) 这样的参数名容易误导，应明确叫 key。
拼写问题：capcity_ 建议改为 capacity_。

建议的基本规范#

map_ 只存真实节点，绝不存 head_/tail_ 哨兵。
put()：存在则更新值并移动到头部；不存在则插入并可能淘汰尾部。
get()：命中则移动到头部并返回值；未命中返回默认值或抛异常。
禁用拷贝，必要时实现移动语义或使用智能指针。

结合当前代码的对照说明#

节点保存 key_ 和 val_，保证淘汰时能从 map_ 删除正确项：

1
template<typename K,typename T>
2
struct Node
3
{
4
  Node* pre_ = nullptr;
5
  Node* next_ = nullptr;
6
  T val_;
7
  K key_;
8
  Node(K key,T val):key_(key),val_(val){}
9
  Node(){
10
    val_ = T{};
11
    key_ = K{};
12
  }
13
};

put() 对已存在 key 会更新 val_ 并移动到头部：

1
auto target = map_.find(key);
2
if(target != map_.end()){
3
  remove_(target->second,false);
4
  target->second->val_ = value;
5
  insert_(head_,target->second);
6
  return;
7
}

新插入节点进入头部并在容量满时淘汰尾部：

1
auto tmp = new Node<K,V>(key,value);
2
map_[key] = tmp;
3
if(nums_ >= capacity_){
4
  Node<K,V>* last = tail_->pre_;
5
  map_.erase(last->key_);
6
  remove_(last);
7
}else{
8
  nums_++;
9
}
10
insert_(head_,tmp);

构造函数禁止 capacity_ == 0：

1
LRUCache(int capacity):capacity_(capacity){
2
  if(capacity == 0) throw runtime_error("capacity can not be zero");
3
  head_ = new Node<K,V>();
4
  tail_ = new Node<K,V>();
5
  head_->next_ = tail_;
6
  tail_->pre_ = head_;
7
}

析构函数按链表顺序释放：

1
~LRUCache(){
2
  auto iter = head_;
3
  while(iter){
4
    auto tmp = iter->next_;
5
    delete iter;
6
    iter = tmp;
7
  }
8
}

源码#

1
#include <iostream>
2
#include <unordered_map>
3
#include <stdexcept>
4

5
using namespace std;
6

7
template<typename K,typename T>
8
struct Node
9
{
10
  Node* pre_ = nullptr;
11
  Node* next_ = nullptr;
12
  T val_;
13
  K key_;
14
  Node(K key,T val):key_(key),val_(val){}
15
  Node(){
16
    val_ = T{};
17
    key_ = K{};
18
  }
19
};
20

21

22

23
template<typename K,typename V>
24
class LRUCache{
25

26
private:
27
  Node<K,V>* head_;
28
  Node<K,V>* tail_;
29
  int capacity_ = 0;
30
  int nums_ = 0;
31
  unordered_map<K,Node<K,V>*> map_;
32

33

34
  void insert_(Node<K,V>* pre,Node<K,V>* target){
35
      auto next = pre->next_;
36
      pre->next_ = target;
37
      target->pre_ = pre;
38
      target->next_ = next;
39
      if(next){
40
        next->pre_ = target;
41
      }
42
  }
43

44
  void remove_(Node<K,V>* target,bool is_delete = true){
45
    auto pre = target->pre_;
46
    auto next = target->next_;
47
    if(pre) pre->next_ = next;
48
    if(next) next->pre_ = pre;
49
    if(is_delete)  delete target;
50
  }
51

52
  LRUCache(const LRUCache& cache) = delete;
53

54
  LRUCache& operator=(const LRUCache& cache)= delete;
55

56
public:
57
  LRUCache(int capacity):capacity_(capacity){
58
    if(capacity == 0) throw runtime_error("capacity can not be zero");
59
    head_ = new Node<K,V>();
60
    tail_ = new Node<K,V>();
61
    head_->next_ = tail_;
62
    tail_->pre_ = head_;
63
  }
64

65
  void put(K key,V value){
66
    auto target = map_.find(key);
67
    if(target != map_.end()){
68
      remove_(target->second,false);
69
      target->second->val_ = value;
70
      insert_(head_,target->second);
71
      return;
72
    }
73
    auto tmp = new Node<K,V>(key,value);
74
    map_[key] = tmp;
75
    if(nums_ >= capacity_){
76
      Node<K,V>* last = tail_->pre_;
77
      map_.erase(last->key_);
78
      remove_(last);
79
    }else{
80
      nums_++;
81
    }
82
    insert_(head_,tmp);
83
  }
84

85
  V get(K key){
86
    auto target = map_.find(key);
87
    if(target == map_.end()){
88
      return V{};
89
    }
90

91
    remove_(target->second,false);
92
    insert_(head_,target->second);
93
    return target->second->val_;
94

95
  }
96

97
  ~LRUCache(){
98
    auto iter = head_;
99
    while(iter){
100
      auto tmp = iter->next_;
101
      delete iter;
102
      iter = tmp;
103
    }
104
  }
105

106
};
107

108

109
int main()
110
{
111
  try
112
  {
113
    LRUCache<int,int> cache(1);
114
    cache.put(1,1);
115
    cache.put(2,2);
116
    cout<<cache.get(2);
117
  }
118
  catch(const std::exception& e)
119
  {
120
    std::cerr << e.what() << '\n';
121
  }
122
}