Skip to content

Instantly share code, notes, and snippets.

@surinoel
Created November 16, 2019 12:29
Show Gist options
  • Save surinoel/c14b1e214c72911061c72c1b9706ac74 to your computer and use it in GitHub Desktop.
Save surinoel/c14b1e214c72911061c72c1b9706ac74 to your computer and use it in GitHub Desktop.
#include <map>
#include <list>
#include <iostream>
using namespace std;
class LRUCache {
private:
list<int> dq;
map<int, list<int>::iterator> m;
int csize;
public:
LRUCache(int);
void refer(int);
void display();
};
LRUCache::LRUCache(int size) {
csize = size;
}
void LRUCache::refer(int x) {
if (m.find(x) == m.end()) {
if (dq.size() == csize) {
int e = dq.back();
dq.pop_back();
m.erase(e);
}
}
else {
dq.erase(m[x]);
}
dq.push_front(x);
m[x] = dq.begin();
}
void LRUCache::display() {
for (auto it = dq.begin(); it != dq.end(); it++)
cout << (*it) << ' ';
cout << '\n';
}
int main() {
LRUCache ca(4);
ca.refer(1);
ca.refer(2);
ca.refer(3);
ca.refer(1);
ca.refer(4);
ca.refer(5);
ca.display();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment