#pragma once
#include <unordered_map>
#include <list>
#include <utility>
template<typename T = int>
class Lru
{
using value_type = typename std::list<std::pair<int, T>>::iterator;
public:
void printList();
void insert(int key, T value);
T query(int key);
private:
size_t capacity_ = 4;
std::list<std::pair<int, T>> list_;//头部为最近最少使用数据
std::unordered_map<int, value_type> hashmap_; //由于插入和查询需要O(1)复杂度，使用哈希表
};
template<typename T>
void Lru<T>::printList()
{
auto it = list_.begin();
for (; it != list_.end(); ++it) {
std::cout << it->first << ", ";
}
std::cout << std::endl;
}
template<typename T>
void Lru<T>::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<typename T>
T Lru<T>::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();
}
