Lru算法C++实现

#pragma once

#include 
#include 
#include 

template
class Lru
{
	using value_type = typename std::list>::iterator;
public:
	void printList();
	void insert(int key, T value);
	T query(int key);
private:
	size_t capacity_ = 4;
	std::list> list_;//头部为最近最少使用数据
	std::unordered_map hashmap_; //由于插入和查询需要O(1)复杂度，使用哈希表
};

template
void Lru::printList()
{
	auto it = list_.begin();
	for (; it != list_.end(); ++it) {
		std::cout << it->first << ", ";
	}
	std::cout << std::endl;
}

template
void Lru::insert(int key, T value)
{
	if (hashmap_.find(key) != hashmap_.end()) return;

	if (hashmap_.size() == capacity_) {
		hashmap_.erase(hashmap_.find(list_.front().first));
		list_.erase(list_.begin());
	}
	list_.push_back(std::make_pair(key, value));
	hashmap_.insert({ key, --list_.end() });
}

template
T Lru::query(int key)
{
	if (hashmap_.find(key) == hashmap_.end()) return -1;
	auto pair = hashmap_.find(key);
	list_.splice(list_.end(), list_, pair->second);
	return pair->second->second;
}

测试

#include "Lru.h"
void LruTest()
{
	Lru<> lru;
	lru.insert(1, 1);
	lru.printList();
	lru.insert(2, 2);
	lru.printList();
	lru.insert(3, 3);
	lru.printList();
	lru.insert(4, 4);
	lru.printList();
	int s = lru.query(2);
	lru.printList();
	lru.insert(5, 5);
	lru.printList();
	int j = lru.query(1);
	lru.printList();
	lru.insert(6, 6);
	lru.printList();
	int k = lru.query(2);
	lru.printList();
	int k1 = lru.query(4);
	lru.printList();
	lru.insert(7, 7);
	lru.printList();
}