如果大家已經學習過了Cache的替換算法和頁面置換算法，大家一定對LRU（Least Recently Used，最近最少使用）不陌生，我們今天來研究下這個算法：

https://leetcode.cn/problems/lru-cache/description/

這里有一個例子：

LRU

LRU（Least Recently Used，最近最少使用）算法是一種常用的緩存淘汰策略，用于在緩存空間有限的情況下決定哪些數據應該被保留，哪些數據應該被移除LRU算法的基本理念是：如果某數據在最近一段時間內沒有被訪問，那么在未來被訪問的可能性也比較低。反之，如果某數據被頻繁訪問，那么它應當被保留在緩存中。

LRU算法的工作原理：

1. 緩存初始化：當緩存初始化時，它是空的。

2. 數據訪問：

• 如果請求的數據已經在緩存中，稱為緩存命中（Hit），則更新該數據項的訪問狀態，表明它最近被使用過。
• 如果請求的數據不在緩存中，稱為緩存未命中（Miss），則需要從主存或其他存儲中加載數據到緩存。

3. 數據淘汰：

• 當緩存已滿，而新的數據需要加入緩存時，LRU算法會選擇最近最少使用的數據項進行淘汰，以便為新數據騰出空間。
• “最近最少使用”的定義是：在當前時刻，從上次訪問到現在時間間隔最長的數據。

實現方法：

LRU算法可以通過多種數據結構來實現，其中最常見的是使用雙向鏈表和哈希表的組合：

• 雙向鏈表：用于維護數據項的訪問順序，最新訪問的數據放在鏈表頭部，最久未訪問的數據放在鏈表尾部。
• 哈希表：用于快速查找數據項在雙向鏈表中的位置。

當數據被訪問時，它從鏈表中的當前位置移動到鏈表頭部。當緩存滿時，鏈表尾部的數據項被移除。

性能考慮：

LRU算法雖然直觀且有效，但在某些情況下可能會有性能開銷，尤其是當數據集非常大時，維護鏈表的插入和刪除操作可能會成為瓶頸。此外，如果數據訪問模式中存在大量突發性的隨機訪問，LRU算法可能無法很好地預測哪些數據是真正需要保留在緩存中的。

盡管如此，LRU仍然是許多緩存系統中首選的淘汰策略，因為它在大多數情況下能夠提供較好的命中率和性能。在軟件和硬件緩存管理中，LRU算法都有廣泛應用。例如，在Web服務器緩存、數據庫查詢緩存、CPU緩存和虛擬內存管理系統中都能見到它的身影。

模擬過程

我們這里用unordered_map和list來模擬：

#pragma once
#include<iostream>
#include<unordered_map>
#include<list>
using namespace std;class LRUCache {
public:LRUCache(int capacity) {}int get(int key) {}void put(int key, int value) {}private:size_t _capacity; //容量//查詢unordered_map<int ,list<pair<int,int>>::iterator> _LRUMap;//插入刪除list<pair<int, int>> _LRUList;
};

unordered_map可以幫助我們查詢是O(1)的時間復雜度，list幫助我們模擬過程，這里我們unordered_map的第二個鍵值對是list的迭代器，這個方便我們直接修改順序是O(1)的操作：

我們來看看：
我們按照這個過程來模擬：

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

這個時候執行了查詢操作：

lRUCache.get(1);    // 返回 1

接下來我們放入了3,3：

lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3}

以此類推，我們可以得出代碼：

#pragma once
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;class LRUCache {
public:// 構造函數，初始化緩存容量LRUCache(int capacity) : _capacity(capacity) {}// 獲取緩存中的值，如果存在則更新其位置至最近使用int get(int key) {// 查找鍵值對應的迭代器auto ret = _LRUMap.find(key);if (ret != _LRUMap.end()) { // 如果找到了鍵值list<pair<int, int>>::iterator it = ret->second;// 將找到的元素移動到列表的前端，表示最近被使用_LRUList.splice(_LRUList.begin(), _LRUList, it);// 返回值return it->second;} else {// 如果沒有找到，返回-1return -1;}}// 插入或更新鍵值對void put(int key, int value) {// 查找鍵值對應的迭代器auto ret = _LRUMap.find(key);if (ret == _LRUMap.end()) { // 如果沒找到，即鍵值不存在// 如果緩存已滿if (_capacity == _LRUList.size()) {// 刪除最舊的元素（列表的最后一個元素）_LRUMap.erase(_LRUList.back().first);_LRUList.pop_back();}// 插入新的鍵值對到列表前端_LRUList.push_front(make_pair(key, value));// 更新或添加鍵值對應的迭代器到哈希表_LRUMap[key] = _LRUList.begin();} else {// 如果鍵值已存在，更新值并移動到列表前端list<pair<int, int>>::iterator it = ret->second;it->second = value; // 更新值// 將元素移動到列表前端_LRUList.splice(_LRUList.begin(), _LRUList, it);}}// 打印緩存內容void Print() {for (auto e : _LRUList) {cout << "key值: " << e.first << " value值: "<< e.second << endl;}cout << endl;}private:size_t _capacity; // 緩存的最大容量// 用于快速查找鍵值對應的迭代器unordered_map<int, list<pair<int, int>>::iterator> _LRUMap;// 存儲鍵值對的有序列表，用于維護最近使用的順序list<pair<int, int>> _LRUList;
};

splice函數

splice是C++標準模板庫(STL)中容器（如std::list, std::forward_list, std::deque）的一個成員函數，用于在容器之間或容器內部移動元素。splice函數允許你將一個容器中的元素或一組連續的元素無縫地插入到另一個相同類型的容器的指定位置，而無需復制或構造元素。這對于需要高效地重新組織元素順序的情況非常有用。

對于std::list和std::forward_list

對于std::list和std::forward_list，splice的用法如下：

基本語法：

void splice(position, x);
void splice(position, x, iterator i);
void splice(position, x, iterator first, iterator last);

• position：在當前容器中插入元素的位置，對于std::list，可以是iterator或const_reference；對于std::forward_list，總是before_begin()。
• x：源容器，必須與當前容器具有相同的類型。
• i：源容器中的單個元素迭代器。
• first, last：源容器中元素范圍的迭代器。

功能描述：

• splice(position, x);：將x容器中的所有元素移動到當前容器的position位置之前。
• splice(position, x, i);：將x容器中由i指向的單個元素移動到當前容器的position位置之前。
• splice(position, x, first, last);：將x容器中由[first, last)區間定義的元素序列移動到當前容器的position位置之前。

示例：

假設我們有兩個std::list<int>容器，list1和list2，我們想把list2中的元素5移動到list1的開始位置：

std::list<int> list1{1, 2, 3, 4};
std::list<int> list2{5, 6, 7, 8};auto it = list2.find(5);
list1.splice(list1.begin(), list2, it);

現在list1看起來應該是{5, 1, 2, 3, 4}，而list2應該是{6, 7, 8}。

注意事項：

• 移動操作是常數時間復雜度的，因此splice非常高效。
• 被移動的元素將從源容器中移除。
• 如果兩個容器共享同一個分配器（例如，它們是同一個容器的不同部分），splice操作不會拋出異常。

對于std::deque，splice的用法與上述略有不同，因為std::deque不允許在中間插入或刪除元素，只能在兩端進行。因此，std::deque的splice只接受before_begin()和end()作為插入位置，而且只能從另一個std::deque中移動元素到當前std::deque的開頭或結尾。

總之，splice是一個強大的工具，可以高效地重新組織容器中的元素，特別是在需要移動大量元素或避免不必要的元素復制時。

具體更多的可以查看官網：

https://legacy.cplusplus.com/