LRU算法 C++版本 (labuladong#326)

yuxiang-zhang · web-flow · commit 7e2163c18af4 · 2020-06-23T11:48:59.000+08:00
diff --git a/高频面试系列/LRU算法.md b/高频面试系列/LRU算法.md
@@ -219,6 +219,65 @@ if (cap == cache.size()) {
 
 ![labuladong](../pictures/labuladong.png)
 
+[yuxiang-zhang](https://github.com/yuxiang-zhang) 提供 C++ 代码：
+
+```cpp
+class LRUCache {
+    // key -> iterator to pair(key, val) in the list
+    unordered_map<int, list<pair<int, int>>::iterator> map;
+    
+    // pair(k1, v1) <-> pair(k2, v2)...
+    list<pair<int, int>> cache;
+    
+    // 最大容量
+    int cap;
+public:
+    LRUCache(int capacity) : cap(capacity) {}
+    
+    int get(int key) {
+        if(map.find(key) == map.end()) {
+            return -1;
+        }
+        
+        int val = map[key]->second;
+        
+        // 利用 put 方法把该数据提前
+        put(key, val);
+        
+        return val;
+    }
+    
+    void put(int key, int value) {
+        pair<int, int> x = {key, value};
+        
+        if(map.find(key) != map.end()) {
+            
+            // 删除旧的节点
+            cache.erase(map[key]);
+            // 新的插到头部
+            cache.emplace_front(x);
+            
+            // 更新 map 中对应的数据
+            map[key] = cache.begin();
+            
+        } else {
+            
+            if(cap == cache.size()) {
+                // 删除链表最后一个数据
+                pair<int, int> last = cache.back(); cache.pop_back();
+                
+                map.erase(last.first);
+            }
+            
+            // 直接添加到头部
+            cache.emplace_front(x);
+            map[key] = cache.begin();
+            
+        }
+    }
+};
+```
+
 [eric wang](https://www.github.com/eric496) 提供 Python3 代码
 
 ```python
@@ -290,4 +349,4 @@ class LRUCache:
 
 [下一篇：二叉搜索树操作集锦](../数据结构系列/二叉搜索树操作集锦.md)
 
-[目录](../README.md#目录)
+[目录](../README.md#目录)
