LRU Cache의 자료구조

페이지 교체 알고리즘 중 하나로 가장 hit율이 좋다고 알려진 LRU는 Least Recently Used의 약자로 가장 늦게 쓰여진 페이지가 교체 대상이 되는 것이다

 

자료구조는 map을 원소로 하는 리스트 기반으로 이뤄져 있다

 

[참고] https://www.geeksforgeeks.org/lru-cache-implementation/

 

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

view raw LRUCache.cpp hosted with ❤ by GitHub