[C++知识库]C++实现LRU缓存

代码

#include<iostream>
#include<list>
#include<unordered_map>
using namespace std;

template <typename k, typename v>
class LRU {
public:
	typedef pair<k, v> Pair;
	typedef list<Pair> List;
	typedef unordered_map<k, typename List::iterator> Hash;

	LRU(int _capcity):capcity(_capcity){};
	~LRU();
	v getn(k key);
	void pushn(k key,v value);
	int LRUsize();
private:
	int capcity;
	List LRUlist;
	Hash cache;
};

template <typename k, typename v>
void LRU<k,v>::pushn(k key, v value) {
	typename Hash::iterator itor = cache.find(key);
	if (itor != cache.end()) {
		LRUlist.erase(itor->second);
		cache.erase(itor);
	}
	LRUlist.push_front(make_pair(key, value));
	cache[key] = LRUlist.begin();
	if (LRUsize() > capcity) {
		k tempk = LRUlist.back().first;
		LRUlist.pop_back();
		cache.erase(tempk);
	}
}

template <typename k, typename v>
v LRU<k, v>::getn(k key) {
	typename Hash::iterator itor = cache.find(key);
	if (itor != cache.end()) {
		pair<k, v> p = make_pair(itor->second->first, itor->second->second);
		LRUlist.erase(itor->second);
		LRUlist.push_front(p);
		cache[key] = LRUlist.begin();
		return p.second;
	}
	return -1;
}

template <typename k, typename v>
int LRU<k, v>::LRUsize() {
	return LRUlist.size();
}

template <typename k, typename v>
LRU<k, v>::~LRU() {
	LRUlist.clear();
	cache.clear();
}

int main() {
	LRU<int,int> lru(3);
	lru.pushn(1, 2);
	lru.pushn(3, 5);
	lru.pushn(1, 3);
	lru.pushn(3, 1);
	cout<<lru.getn(1)<<endl;
	return 0;
}