C++實現(xiàn)LRU緩存的操作方法
LRU的概念
LRU（Least Recently Used，最近最少使用）是一種常用的緩存淘汰策略，主要目的是在緩存空間有限的情況下，優(yōu)先淘汰那些最長時間沒有被訪問的數(shù)據(jù)項。LRU 策略的核心思想是：
- 緩存空間有限：緩存只能存儲一定數(shù)量的數(shù)據(jù)項。
- 淘汰最不常用的數(shù)據(jù)：當緩存滿時，優(yōu)先淘汰那些最近最少被訪問的數(shù)據(jù)項。
- 訪問記錄：每次數(shù)據(jù)項被訪問時，都會更新其訪問記錄，使得最近訪問的數(shù)據(jù)項保留在緩存中。
- 數(shù)據(jù)替換：當需要加載新數(shù)據(jù)項到緩存中，但緩存已滿時，會根據(jù)LRU策略淘汰一個或多個數(shù)據(jù)項，為新數(shù)據(jù)項騰出空間。
- 動態(tài)調(diào)整：隨著數(shù)據(jù)訪問模式的變化，LRU策略可以動態(tài)調(diào)整緩存中的數(shù)據(jù)項，以適應訪問模式的變化。
在實現(xiàn)LRU緩存時，通常會使用數(shù)據(jù)結(jié)構(gòu)如哈希表和雙向鏈表。哈希表用于快速定位緩存中的數(shù)據(jù)項，而雙向鏈表則用于維護數(shù)據(jù)項的訪問順序。每次訪問數(shù)據(jù)項時，都會將其移動到鏈表的頭部，表示它是最近被訪問的。當需要淘汰數(shù)據(jù)時，直接從鏈表的尾部開始淘汰即可。
LRU策略在許多場景中都非常有用，比如操作系統(tǒng)的頁面置換、數(shù)據(jù)庫的查詢緩存、Web服務器的頁面緩存等。它可以幫助系統(tǒng)更有效地利用有限的緩存資源，提高系統(tǒng)的整體性能。
別急，我們先學實現(xiàn)LRU要用的哈希表和雙向鏈表
哈希表（unordered_map）
在C++中，unordered_map 是標準模板庫（STL）中的一個關聯(lián)容器，它基于哈希表的實現(xiàn)。它存儲了鍵值對，允許通過鍵快速訪問和修改值。unordered_map 提供了平均常數(shù)時間復雜度的訪問、插入和刪除操作。
主要特性
- 基于哈希表：通過哈希函數(shù)將鍵映射到存儲位置，實現(xiàn)快速查找。
- 鍵不重復：每個鍵在容器中是唯一的。
- 無序存儲：元素的存儲順序不依賴于插入順序，因此迭代器的遍歷順序可能與插入順序不同。
常用操作
- 構(gòu)造和初始化：
unordered_map()：創(chuàng)建一個空的unordered_map。unordered_map(initializer_list<value_type>)：使用初始化列表創(chuàng)建unordered_map。
- 插入操作：
insert(value_type)：插入一個鍵值對。insert(initializer_list<value_type>)：插入多個鍵值對。
- 訪問操作：
operator[]：通過鍵訪問對應的值，如果鍵不存在，則插入一個新元素。at(key)：通過鍵訪問對應的值，如果鍵不存在，則拋出std::out_of_range異常。
- 查找操作：
find(key)：查找鍵是否存在，返回一個迭代器。count(key)：返回鍵出現(xiàn)的次數(shù)（對于unordered_map總是返回 0 或 1）。
- 刪除操作：
erase(it)：刪除迭代器it指向的元素。erase(first, last)：刪除從first到last（不包括last）范圍內(nèi)的所有元素。erase(key)：刪除指定鍵的所有元素。
- 大小和容量：
size()：返回容器中元素的數(shù)量。empty()：如果容器為空，返回true。
- 迭代器：
begin()：返回指向容器開始的迭代器。end()：返回指向容器結(jié)束的迭代器。 示例代碼
以下是使用 unordered_map 的一個簡單示例：
#include <iostream>
#include <unordered_map>
int main() {
// 創(chuàng)建一個 unordered_map，鍵為 int，值為 string
unordered_map<int, string> umap;
// 插入元素
umap[1] = "one";
umap[2] = "two";
umap[3] = "three";
// 訪問并打印元素
for (const auto& pair : umap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 訪問特定鍵的值
try {
std::cout << "Value for key 2: " << umap.at(2) << std::endl;
} catch (const std::out_of_range& e) {
std::cerr << e.what() << std::endl;
}
// 查找鍵是否存在
auto it = umap.find(3);
if (it != umap.end()) {
std::cout << "Key 3 found, value: " << it->second << std::endl;
}
// 刪除元素
umap.erase(2);
std::cout << "After erasing key 2:" << std::endl;
for (const auto& pair : umap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}輸出：
1: one
2: two
3: three
Value for key 2: two
Key 3 found, value: three
After erasing key 2:
1: one
3: three
在這個示例中：
- 創(chuàng)建了一個
unordered_map并插入了一些鍵值對。 - 遍歷并打印了
unordered_map中的所有元素。 - 使用
at()方法安全地訪問特定鍵的值。 - 使用
find()方法查找鍵是否存在，并訪問對應的值。 - 使用
erase()方法刪除了鍵為 2 的元素，并再次打印了剩余的元素。
雙向鏈表（list）
在C++中，list 是標準模板庫（STL）中的一個容器類，它提供了雙向鏈表的實現(xiàn)。與數(shù)組或向量（vector）不同，list 允許在任意位置高效地插入和刪除元素，而不需要移動其他元素。
以下是 list 的一些主要特性和常用操作：
特性
- 雙向鏈表：每個元素都是鏈表中的一個節(jié)點，可以從前向后或從后向前遍歷。
- 動態(tài)大小：
list的大小可以根據(jù)需要動態(tài)變化，不需要預先定義大小。 - 插入和刪除操作：可以在常數(shù)時間內(nèi)在任意位置插入或刪除元素，不需要像
vector那樣移動其他元素。
常用操作
- 插入操作：
push_front(value)：在鏈表頭部插入一個元素。push_back(value)：在鏈表尾部插入一個元素。insert(position, value)：在指定位置插入一個元素。insert(position, n, value)：在指定位置插入n個相同的元素。insert(position, first, last)：在指定位置插入一個范圍內(nèi)的元素。
- 刪除操作：
pop_front()：刪除鏈表頭部的元素。pop_back()：刪除鏈表尾部的元素。erase(position)：刪除指定位置的元素。erase(first, last)：刪除從first到last（不包括last）范圍內(nèi)的所有元素。
- 訪問操作：
front()：返回鏈表頭部的元素。back()：返回鏈表尾部的元素。
- 迭代器：
begin()：返回指向鏈表頭部的迭代器。end()：返回指向鏈表尾部的迭代器。
- 大小和容量：
size()：返回鏈表中元素的數(shù)量。empty()：如果鏈表為空，返回true。
示例代碼
以下是使用 list 的一個簡單示例：
#include <iostream>
#include <list>
int main() {
list<int> myList;
// 向鏈表中添加元素
myList.push_back(10);
myList.push_back(20);
myList.push_front(5);
// 訪問并打印鏈表中的元素
for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 刪除頭部元素
myList.pop_front();
std::cout << "After popping front: ";
for (auto it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 刪除尾部元素
myList.pop_back();
std::cout << "After popping back: ";
for (auto it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}輸出：
5 10 20
After popping front: 10 20
After popping back: 10
在這個示例中，我們創(chuàng)建了一個 list 并添加了一些整數(shù)元素。然后，我們遍歷并打印鏈表中的元素，刪除頭部和尾部的元素，并再次打印鏈表中的元素。
到這里，你已經(jīng)掌握實現(xiàn)LRU緩存的兩個條件了，馬上你就要成功了?。?！
真的，不信你往下看！
LRU緩存（C++）
#include <iostream>
#include <list>
#include <unordered_map>
// 使用 using namespace std; 來簡化代碼，避免重復書寫 std:: 前綴
using namespace std;
// LRUCache 類定義
class LRUCache {
private:
int capacity; // 緩存的容量
list<int> keys; // 使用雙向鏈表存儲鍵，保持訪問順序
unordered_map<int, pair<int, list<int>::iterator>> cache; // 存儲鍵值對和對應的鏈表迭代器
public:
// 構(gòu)造函數(shù)，初始化緩存容量
LRUCache(int capacity) : capacity(capacity) {}
// 獲取緩存中鍵對應的值
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) {
return -1; // 如果鍵不存在，返回 -1
}
// 更新訪問順序，將該鍵移動到鏈表頭部
keys.erase(it->second.second);
keys.push_front(key);
it->second.second = keys.begin();
return it->second.first; // 返回鍵對應的值
}
// 插入或更新緩存中的鍵值對
void put(int key, int value) {
if (cache.size() >= capacity && cache.find(key) == cache.end()) {
// 如果緩存已滿且鍵不存在，淘汰最不常用的鍵（鏈表尾部的鍵）
auto last = keys.back();
cache.erase(cache.find(last));
keys.pop_back();
}
// 插入或更新鍵值對，并更新訪問順序
cache[key] = {value, keys.insert(keys.begin(), key)};
}
};
int main() {
// 創(chuàng)建一個容量為 2 的 LRU 緩存
LRUCache cache(2);
// 插入鍵值對 (1, 1)
cache.put(1, 1);
// 訪問鍵 1，輸出其值
cout << "get(1) = " << cache.get(1) << endl; // 返回 1
// 插入鍵值對 (2, 2)
cache.put(2, 2);
// 訪問鍵 2，輸出其值
cout << "get(2) = " << cache.get(2) << endl; // 返回 2
// 插入鍵值對 (3, 3)，由于緩存已滿，鍵 1 被淘汰
cache.put(3, 3);
// 訪問鍵 1，由于已被淘汰，返回 -1
cout << "get(1) = " << cache.get(1) << endl; // 返回 -1
// 訪問鍵 3，輸出其值
cout << "get(3) = " << cache.get(3) << endl; // 返回 3
// 插入鍵值對 (4, 4)，由于緩存已滿，鍵 2 被淘汰
cache.put(4, 4);
// 訪問鍵 1，由于已被淘汰，返回 -1
cout << "get(1) = " << cache.get(1) << endl; // 返回 -1
// 訪問鍵 3，輸出其值
cout << "get(3) = " << cache.get(3) << endl; // 返回 3
// 訪問鍵 2，由于已被淘汰，返回 -1
cout << "get(2) = " << cache.get(2) << endl; // 返回 -1
// 訪問鍵 4，輸出其值
cout << "get(4) = " << cache.get(4) << endl; // 返回 4
return 0;
}這段代碼首先定義了一個 LRUCache 類，該類使用 unordered_map 和 list 來實現(xiàn) LRU 緩存機制。get 方法用于獲取緩存中的值，如果鍵存在，則返回其值并更新訪問順序；如果鍵不存在，則返回 -1。put 方法用于插入或更新緩存中的鍵值對，如果緩存已滿，則淘汰最不常用的鍵（鏈表尾部的鍵）。在 main 函數(shù)中，創(chuàng)建了一個 LRUCache 對象并進行了一些操作來演示其功能。
什么？看不懂？沒關系，結(jié)合下面的過程看，你應該就明白了！
初始化狀態(tài)
Cache: {}
Keys: []執(zhí)行 cache.put(1, 1)
Cache: {1: (1, it1)}
Keys: [1]執(zhí)行 cache.put(2, 2)
Cache: {1: (1, it1), 2: (2, it2)}
Keys: [2, 1] (2 最近使用，1 最少使用)執(zhí)行 cache.put(3, 3)
緩存已滿，淘汰鍵 1
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2] (3 最近使用，2 次之)執(zhí)行 cache.get(1)
鍵 1 不存在，返回 -1
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]執(zhí)行 cache.get(3)
鍵 3 存在，返回 3，并更新為最近使用
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]執(zhí)行 cache.put(4, 4)
緩存已滿，淘汰鍵 2
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3] (4 最近使用，3 次之)執(zhí)行 cache.get(1)
鍵 1 不存在，返回 -1
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]執(zhí)行 cache.get(3)
鍵 3 存在，返回 3，并更新為最近使用
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]執(zhí)行 cache.get(2)
鍵 2 不存在，返回 -1
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]執(zhí)行 cache.get(4)
鍵 4 存在，返回 4，并更新為最近使用
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]至此，你就算沒有臺明白，也一定了解LRU了。收藏可以方便下次鞏固哦?。。?！
到此這篇關于C++實現(xiàn)LRU緩存的文章就介紹到這了,更多相關C++ LRU緩存內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++ 中快排的遞歸和非遞歸實現(xiàn)的相關資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C++vector自定義大小方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
case穿透是一個既實用又容易引發(fā)錯誤的特性,下面就來介紹一下case 穿透的原理、應用場景、注意事項及如何避免常見錯誤,感興趣的可以了解一下2025-06-06
下個迭代有個任務很有趣,用大量的線程去訪問一個接口,直至其崩潰為止,這就需要多線程的知識,這也不是什么難事,本文總結(jié)一下C++中的多線程方法std、boost、pthread、windows?api,感興趣的朋友可以參考下2024-01-01
這篇文章主要給大家介紹了關于在C++中如何移除序列中連續(xù)重復的特定值，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-01-01
C語言數(shù)據(jù)結(jié)構(gòu)之棧和隊列的實現(xiàn)及應用
棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實現(xiàn)方式。本文將以順序結(jié)構(gòu)實現(xiàn)棧，鏈表方式實現(xiàn)隊列，感興趣的小伙伴快跟隨小編一起學習一下吧2022-08-08
下面小編就為大家?guī)硪黄钊肜斫釩++移位運算符。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-05-05
這篇文章主要為大家詳細介紹了C語言中幾種進程間通訊的方式，文中的示例代碼講解詳細，?對我們學習或工作有一定的借鑒價值，需要的可以參考一下2022-08-08
這篇文章主要介紹了C++編程中類模板的三種特化,需要的朋友可以參考下2016-01-01
C語言實現(xiàn)五子棋對戰(zhàn)系統(tǒng)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)五子棋對戰(zhàn)系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05