在觀看了多個在線資源后，我已經實作了 LRU 快取，但我無法理解為什么代碼輸出值“alpha”為 3，請建議如何在 LRU 快取實作中解決這個問題。我檢查了多個在線資源，但它們都是用于實作 int 到 int 的映射，這里我想將輸入作為整數并存盤一個尚未在任何地方覆寫的字串
這是代碼：
#include <iostream>
#include<bits/stdc .h>
// we have used doubly linked list as it was readily availaible in the c stl library
#include <list>
// we do not need ordered map , unordered map is enough for hashing
#include <unordered_map>
using namespace std;
class LRU_Cache{
public:
// this cache stores strings
// integers are mapped to strings , i.e. we can access data using integers
list<string> L;
unordered_map<int,list<string>::iterator > M;
int capacity ;
LRU_Cache(int cap){
capacity = cap;
L.clear();
M.clear();
}
int size(){
return capacity;
}
void feedin(int key , string data){
// if key not present in cache already
if(M.find(key)==M.end()){
// when cache is full then remove last then insert else just insert
// so we just need if rather than if else
if(L.size()==capacity){
// remove the last element first from map then from list
// removing from map
for(auto it:M){
if((it.second) == L.end()){
// M[it.first] = M.end();
M.erase(it.first);//it.first
break;
}
}
// removing from list
L.pop_back();
}
// key is not present and cache is not full case
else{
}
// now insertion
L.push_front(data);
M[key]=L.begin();
return;
}
// key is present in cache already
else{
// erase the already present data for that key in the list
L.erase(M[key]);
// add the data to the list
L.push_front(data);
// reassign the value of iterator in the map for that key
M[key]=L.begin();
// we do not need to remove the last value here ,
// since size of cache remains same after this operation
return;
}
}
string gettin(int key){
if(M.find(key)==M.end()){
return "0";
}
else{
return *M[key];
}
}
};
int main()
{
// Declaring a LRU Cache
LRU_Cache lru1(2);
// Checking the size
cout<<"The size of this LRU Cache is : " <<lru1.size()<<endl;
// Adding data to it
lru1.feedin(3,"beta");
lru1.feedin(1,"alpha");
lru1.feedin(8,"gamma");
// checking the data now
cout<<lru1.gettin(1)<<endl;
cout<<lru1.gettin(3)<<endl;
cout<<lru1.gettin(6)<<endl;
cout<<lru1.gettin(8)<<endl;
return 0;
}
這是輸出
阿爾法伽馬 0 伽馬
編輯：現在已經解決了疑問，現在可以在https://github.com/ayush-agarwal-0502/LRU-Cache-Implementation上為任何試圖實作 LRU 快取并需要解釋或代碼的人提供代碼
uj5u.com熱心網友回復：
在feedin替換
if((it.second) == L.end())
和
if((it.second) == --L.end())
并確保capacity永遠不能為零。這不應該有太大的限制，因為沒有任何意義的 LRU 快取不能快取任何東西。
解釋：
我認為錯誤在于相信L.end()回傳一個迭代器，該迭代器參考L. 它沒有。end()回傳一個標記串列末尾的哨兵。它不對應于串列中的任何元素，這就是為什么它可以用作搜索中未找到的專案的原因。
在feedin,
if((it.second) == L.end())
將L存盤M的迭代器與保證不在 in 的迭代器進行比較L，因此不會在M. 什么都找不到。要獲得 中最后一項的迭代器L，您需要--L.end(). 請注意，--L.end()當串列不為空時有效，由capacity大于 0 保證。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488645.html