Реализация кэша LRU с использованием std :: map и std :: list в c ++. Не могу получить обязательный выход ⇐ C++

[Anonymous]

Я пытаюсь написать код C ++ для реализации кэша. Кэш использует наименьшую недавно используемую политику, объясняемая поведением:

• Если в кэше есть способность хранить 5 клавиш, такие как 5 3 2 1 4 , если следующий ключ = 1 Походит в качестве хит, порядок кэша становится 1 5 3 2 4 . 2 .

Код, который я написал ниже, работает для тестового примера 1 и его вывода, но не для тестового примера 2 и его вывода. Я показал свой код, входы и ожидаемые выходы ниже.

Код: Выделить всё

#include 
#include 
#include 
#include 

using namespace std;

struct Node {
int value, key;
Node (int k,int v):value(v),key(k){};
}typedef Node;

class Cache{
protected :
list  l;
map mp;
int cp;
virtual void set(int,int) =0;
virtual int get(int)=0;

}typedef Cache;

class LRUCache:public Cache{

void removeback(){
mp.erase(--l.end()->key);
l.pop_back();
}
void addatfront(int k, int v) {
Node *node = new Node(k,v);
if (mp.size() == cp)
removeback();
//l.push_front({k,v});
l.push_front(*node);
mp[k] = l.begin()
}
void movetohead(list::iterator  arg, int new_val){
(*arg).value = new_val;
l.splice(l.begin(),l,arg);
mp[arg->key]= l.begin();
}
public:
LRUCache(int &cap){
cp = cap;
}
void set(int k,int v){
if (mp.find(k)!=mp.end()){
if (mp.size()>1)
movetohead(mp[k],v);
else
l.begin()->value = v;
}
else
addatfront(k,v);
}

int get (int k){
if (mp.find(k)!=mp.end())
return mp[k]->value;
return -1;
}
}typedef LRUCache;

int main()
{
int n, capacity,i;
cin>> n>> capacity;
LRUCache l(capacity);
for (i =0;i< n;i++){
string command;
cin>> command;
if (command == "get"){
int key;
cin >> key;
cout key>>value;
l.set(key, value);
}
}
return 0;
}
< /code>
Тестовый пример ввода 1: < /p>
3 1
set 1 2
get 1
get 2
< /code>
output: < /p>
2
-1
< /code>
Тестовый пример ввода 2: < /p>
22 4
set 7 1905
get 16
get 4
set 20 1738
get 14
set 12 320
set 4 1382
set 11 1049
set 8 1372
get 11
set 7 937
set 9 654
set 11 1727
get 1
set 13 1945
get 5
get 15
set 6 1668
set 8 270
set 1 604
get 20
get 5`
< /code>
output: < /p>
-1
-1
-1
1049
-1
-1
-1
1738
-1

В фактическом выходе я вижу -1 вместо 1738 для второго по линии вывода.


Подробнее здесь: https://stackoverflow.com/questions/797 ... required-o