54 lines
1.5 KiB
C++
54 lines
1.5 KiB
C++
#include <iostream>
|
|
#include <unordered_map>
|
|
#include <list>
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <memory>
|
|
|
|
template<typename Key, typename Value>
|
|
class LRUCache {
|
|
public:
|
|
LRUCache(size_t capacity) : capacity_(capacity) {
|
|
assert(capacity > 0);
|
|
}
|
|
|
|
std::shared_ptr<Value> get(const Key& key) {
|
|
auto it = cache_.find(key);
|
|
if (it == cache_.end()) {
|
|
std::shared_ptr<Value> ptr(new Value());
|
|
put(key, ptr);
|
|
return ptr;
|
|
}
|
|
touch(it);
|
|
return it->second.first;
|
|
}
|
|
private:
|
|
void put(const Key& key, const std::shared_ptr<Value>& value) {
|
|
auto it = cache_.find(key);
|
|
if (it != cache_.end()) {
|
|
touch(it);
|
|
it->second.first = value;
|
|
}
|
|
else {
|
|
if (cache_.size() == capacity_) {
|
|
cache_.erase(usage_.back());
|
|
usage_.pop_back();
|
|
}
|
|
usage_.push_front(key);
|
|
cache_[key] = { value, usage_.begin() };
|
|
}
|
|
}
|
|
typedef typename std::list<Key>::iterator ListIt;
|
|
std::unordered_map<Key, std::pair<std::shared_ptr<Value>, ListIt>> cache_;
|
|
std::list<Key> usage_;
|
|
size_t capacity_;
|
|
|
|
void touch(typename std::unordered_map<Key, std::pair<std::shared_ptr<Value>, ListIt>>::iterator it) {
|
|
usage_.erase(it->second.second);
|
|
usage_.push_front(it->first);
|
|
it->second.second = usage_.begin();
|
|
}
|
|
};
|
|
|
|
|
|
#pragma once |