LRUCache.cpp

#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;
}