Data-Structures-and-Algorithms/CPP/structures/LRU.cpp at main · codemistic/Data-Structures-and-Algorithms · GitHub

Name: Data-Structures-and-Algorithms/CPP/structures/LRU.cpp at main · codemistic/Data-Structures-and-Algorithms · GitHub
Rating: 4.6 (7684 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
usingnamespacestd;
unordered_map<int, list<int>::iterator> mp;
list<int> q;
int sz;
voidinsert(int x)
{

// if not present
if (mp.find(x) == mp.end())
 {
if (q.size() == sz)
 {
int last = q.back();
 q.pop_back();
 mp.erase(last);
 }
 }
// if present
else
 mp.erase(x);

 q.push_front(x);
 mp[x] = q.begin();
}

voiddisplay()
{

for (auto it = q.begin(); it != q.end(); it++)
 cout << *it << "";
}

intmain()
{

 cin >> sz;
insert(1);
insert(2);
insert(3);
insert(1);
insert(4);
insert(5);
display();
return0;
}