LRU的概念

LRU（Least Recently Used，最近最少使用）是一種常用的緩存淘汰策略，主要目的是在緩存空間有限的情況下，優(yōu)先淘汰那些最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)的數(shù)據(jù)項(xiàng)。LRU 策略的核心思想是：

• 緩存空間有限：緩存只能存儲(chǔ)一定數(shù)量的數(shù)據(jù)項(xiàng)。
• 淘汰最不常用的數(shù)據(jù)：當(dāng)緩存滿時(shí)，優(yōu)先淘汰那些最近最少被訪問(wèn)的數(shù)據(jù)項(xiàng)。
• 訪問(wèn)記錄：每次數(shù)據(jù)項(xiàng)被訪問(wèn)時(shí)，都會(huì)更新其訪問(wèn)記錄，使得最近訪問(wèn)的數(shù)據(jù)項(xiàng)保留在緩存中。
• 數(shù)據(jù)替換：當(dāng)需要加載新數(shù)據(jù)項(xiàng)到緩存中，但緩存已滿時(shí)，會(huì)根據(jù)LRU策略淘汰一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)，為新數(shù)據(jù)項(xiàng)騰出空間。
• 動(dòng)態(tài)調(diào)整：隨著數(shù)據(jù)訪問(wèn)模式的變化，LRU策略可以動(dòng)態(tài)調(diào)整緩存中的數(shù)據(jù)項(xiàng)，以適應(yīng)訪問(wèn)模式的變化。

在實(shí)現(xiàn)LRU緩存時(shí)，通常會(huì)使用數(shù)據(jù)結(jié)構(gòu)如哈希表和雙向鏈表。哈希表用于快速定位緩存中的數(shù)據(jù)項(xiàng)，而雙向鏈表則用于維護(hù)數(shù)據(jù)項(xiàng)的訪問(wèn)順序。每次訪問(wèn)數(shù)據(jù)項(xiàng)時(shí)，都會(huì)將其移動(dòng)到鏈表的頭部，表示它是最近被訪問(wèn)的。當(dāng)需要淘汰數(shù)據(jù)時(shí)，直接從鏈表的尾部開(kāi)始淘汰即可。

LRU策略在許多場(chǎng)景中都非常有用，比如操作系統(tǒng)的頁(yè)面置換、數(shù)據(jù)庫(kù)的查詢緩存、Web服務(wù)器的頁(yè)面緩存等。它可以幫助系統(tǒng)更有效地利用有限的緩存資源，提高系統(tǒng)的整體性能。
別急，我們先學(xué)實(shí)現(xiàn)LRU要用的哈希表和雙向鏈表

哈希表（unordered_map）

在C++中，unordered_map 是標(biāo)準(zhǔn)模板庫(kù)（STL）中的一個(gè)關(guān)聯(lián)容器，它基于哈希表的實(shí)現(xiàn)。它存儲(chǔ)了鍵值對(duì)，允許通過(guò)鍵快速訪問(wèn)和修改值。unordered_map 提供了平均常數(shù)時(shí)間復(fù)雜度的訪問(wèn)、插入和刪除操作。

主要特性

• 基于哈希表：通過(guò)哈希函數(shù)將鍵映射到存儲(chǔ)位置，實(shí)現(xiàn)快速查找。
• 鍵不重復(fù)：每個(gè)鍵在容器中是唯一的。
• 無(wú)序存儲(chǔ)：元素的存儲(chǔ)順序不依賴于插入順序，因此迭代器的遍歷順序可能與插入順序不同。

常用操作

• 構(gòu)造和初始化：
  • unordered_map()：創(chuàng)建一個(gè)空的 unordered_map。
  • unordered_map(initializer_list<value_type>)：使用初始化列表創(chuàng)建 unordered_map。
• 插入操作：
  • insert(value_type)：插入一個(gè)鍵值對(duì)。
  • insert(initializer_list<value_type>)：插入多個(gè)鍵值對(duì)。
• 訪問(wèn)操作：
  • operator[]：通過(guò)鍵訪問(wèn)對(duì)應(yīng)的值，如果鍵不存在，則插入一個(gè)新元素。
  • at(key)：通過(guò)鍵訪問(wèn)對(duì)應(yīng)的值，如果鍵不存在，則拋出 std::out_of_range 異常。
• 查找操作：
  • find(key)：查找鍵是否存在，返回一個(gè)迭代器。
  • count(key)：返回鍵出現(xiàn)的次數(shù)（對(duì)于 unordered_map 總是返回 0 或 1）。
• 刪除操作：
  • erase(it)：刪除迭代器 it 指向的元素。
  • erase(first, last)：刪除從 first 到 last（不包括 last）范圍內(nèi)的所有元素。
  • erase(key)：刪除指定鍵的所有元素。
• 大小和容量：
  • size()：返回容器中元素的數(shù)量。
  • empty()：如果容器為空，返回 true。
• 迭代器：
  • begin()：返回指向容器開(kāi)始的迭代器。
  • end()：返回指向容器結(jié)束的迭代器。 示例代碼

以下是使用 unordered_map 的一個(gè)簡(jiǎn)單示例：

#include <iostream>
#include <unordered_map>
int main() {
    // 創(chuàng)建一個(gè) unordered_map，鍵為 int，值為 string
    unordered_map<int, string> umap;
    // 插入元素
    umap[1] = "one";
    umap[2] = "two";
    umap[3] = "three";
    // 訪問(wèn)并打印元素
    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 訪問(wèn)特定鍵的值
    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

在這個(gè)示例中：

• 創(chuàng)建了一個(gè) unordered_map 并插入了一些鍵值對(duì)。
• 遍歷并打印了 unordered_map 中的所有元素。
• 使用 at() 方法安全地訪問(wèn)特定鍵的值。
• 使用 find() 方法查找鍵是否存在，并訪問(wèn)對(duì)應(yīng)的值。
• 使用 erase() 方法刪除了鍵為 2 的元素，并再次打印了剩余的元素。

雙向鏈表（list）

在C++中，list 是標(biāo)準(zhǔn)模板庫(kù)（STL）中的一個(gè)容器類，它提供了雙向鏈表的實(shí)現(xiàn)。與數(shù)組或向量（vector）不同，list 允許在任意位置高效地插入和刪除元素，而不需要移動(dòng)其他元素。

以下是 list 的一些主要特性和常用操作：

特性

• 雙向鏈表：每個(gè)元素都是鏈表中的一個(gè)節(jié)點(diǎn)，可以從前向后或從后向前遍歷。
• 動(dòng)態(tài)大小：list 的大小可以根據(jù)需要?jiǎng)討B(tài)變化，不需要預(yù)先定義大小。
• 插入和刪除操作：可以在常數(shù)時(shí)間內(nèi)在任意位置插入或刪除元素，不需要像 vector 那樣移動(dòng)其他元素。

常用操作

• 插入操作：
  • push_front(value)：在鏈表頭部插入一個(gè)元素。
  • push_back(value)：在鏈表尾部插入一個(gè)元素。
  • insert(position, value)：在指定位置插入一個(gè)元素。
  • insert(position, n, value)：在指定位置插入 n 個(gè)相同的元素。
  • insert(position, first, last)：在指定位置插入一個(gè)范圍內(nèi)的元素。
• 刪除操作：
  • pop_front()：刪除鏈表頭部的元素。
  • pop_back()：刪除鏈表尾部的元素。
  • erase(position)：刪除指定位置的元素。
  • erase(first, last)：刪除從 first 到 last（不包括 last）范圍內(nèi)的所有元素。
• 訪問(wèn)操作：
  • front()：返回鏈表頭部的元素。
  • back()：返回鏈表尾部的元素。
• 迭代器：
  • begin()：返回指向鏈表頭部的迭代器。
  • end()：返回指向鏈表尾部的迭代器。
• 大小和容量：
  • size()：返回鏈表中元素的數(shù)量。
  • empty()：如果鏈表為空，返回 true。

示例代碼

以下是使用 list 的一個(gè)簡(jiǎn)單示例：

#include <iostream>
#include <list>
int main() {
    list<int> myList;
    // 向鏈表中添加元素
    myList.push_back(10);
    myList.push_back(20);
    myList.push_front(5);
    // 訪問(wèn)并打印鏈表中的元素
    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 

在這個(gè)示例中，我們創(chuàng)建了一個(gè) list 并添加了一些整數(shù)元素。然后，我們遍歷并打印鏈表中的元素，刪除頭部和尾部的元素，并再次打印鏈表中的元素。

到這里，你已經(jīng)掌握實(shí)現(xiàn)LRU緩存的兩個(gè)條件了，馬上你就要成功了！?。?/p>

真的，不信你往下看！

LRU緩存（C++）

#include <iostream>
#include <list>
#include <unordered_map>
// 使用 using namespace std; 來(lái)簡(jiǎn)化代碼，避免重復(fù)書寫 std:: 前綴
using namespace std;
// LRUCache 類定義
class LRUCache {
private:
    int capacity;  // 緩存的容量
    list<int> keys;  // 使用雙向鏈表存儲(chǔ)鍵，保持訪問(wèn)順序
    unordered_map<int, pair<int, list<int>::iterator>> cache;  // 存儲(chǔ)鍵值對(duì)和對(duì)應(yīng)的鏈表迭代器
public:
    // 構(gòu)造函數(shù)，初始化緩存容量
    LRUCache(int capacity) : capacity(capacity) {}
    // 獲取緩存中鍵對(duì)應(yīng)的值
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;  // 如果鍵不存在，返回 -1
        }
        // 更新訪問(wèn)順序，將該鍵移動(dòng)到鏈表頭部
        keys.erase(it->second.second);
        keys.push_front(key);
        it->second.second = keys.begin();
        return it->second.first;  // 返回鍵對(duì)應(yīng)的值
    }
    // 插入或更新緩存中的鍵值對(duì)
    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();
        }
        // 插入或更新鍵值對(duì)，并更新訪問(wèn)順序
        cache[key] = {value, keys.insert(keys.begin(), key)};
    }
};
int main() {
    // 創(chuàng)建一個(gè)容量為 2 的 LRU 緩存
    LRUCache cache(2);
    // 插入鍵值對(duì) (1, 1)
    cache.put(1, 1);
    // 訪問(wèn)鍵 1，輸出其值
    cout << "get(1) = " << cache.get(1) << endl; // 返回 1
    // 插入鍵值對(duì) (2, 2)
    cache.put(2, 2);
    // 訪問(wèn)鍵 2，輸出其值
    cout << "get(2) = " << cache.get(2) << endl; // 返回 2
    // 插入鍵值對(duì) (3, 3)，由于緩存已滿，鍵 1 被淘汰
    cache.put(3, 3);
    // 訪問(wèn)鍵 1，由于已被淘汰，返回 -1
    cout << "get(1) = " << cache.get(1) << endl; // 返回 -1
    // 訪問(wèn)鍵 3，輸出其值
    cout << "get(3) = " << cache.get(3) << endl; // 返回 3
    // 插入鍵值對(duì) (4, 4)，由于緩存已滿，鍵 2 被淘汰
    cache.put(4, 4);
    // 訪問(wèn)鍵 1，由于已被淘汰，返回 -1
    cout << "get(1) = " << cache.get(1) << endl; // 返回 -1
    // 訪問(wèn)鍵 3，輸出其值
    cout << "get(3) = " << cache.get(3) << endl; // 返回 3
    // 訪問(wèn)鍵 2，由于已被淘汰，返回 -1
    cout << "get(2) = " << cache.get(2) << endl; // 返回 -1
    // 訪問(wèn)鍵 4，輸出其值
    cout << "get(4) = " << cache.get(4) << endl; // 返回 4
    return 0;
}

這段代碼首先定義了一個(gè) LRUCache 類，該類使用 unordered_map 和 list 來(lái)實(shí)現(xiàn) LRU 緩存機(jī)制。get 方法用于獲取緩存中的值，如果鍵存在，則返回其值并更新訪問(wèn)順序；如果鍵不存在，則返回 -1。put 方法用于插入或更新緩存中的鍵值對(duì)，如果緩存已滿，則淘汰最不常用的鍵（鏈表尾部的鍵）。在 main 函數(shù)中，創(chuàng)建了一個(gè) LRUCache 對(duì)象并進(jìn)行了一些操作來(lái)演示其功能。

什么？看不懂？沒(méi)關(guān)系，結(jié)合下面的過(guò)程看，你應(yīng)該就明白了！

初始化狀態(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]

至此，你就算沒(méi)有臺(tái)明白，也一定了解LRU了。收藏可以方便下次鞏固哦?。。。?/p>

到此這篇關(guān)于C++實(shí)現(xiàn)LRU緩存的文章就介紹到這了,更多相關(guān)C++ LRU緩存內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論