>>107953301
first pass, would need more time to make it faster
class LRUCache {
public:
using lru_iterator = std::list<std::pair<int, int>>::iterator;
std::list<std::pair<int, int>> lru;
std::unordered_map<int, lru_iterator> cache;
int cap;
LRUCache(int capacity) {
cap = capacity;
}
void use(lru_iterator& it2)
{
auto i3 = lru.emplace(lru.end(), *it2);
lru.erase(it2);
it2 = i3;
}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end())
return -1;
else
{
use(it->second);
return it->second->second;
}
}
void put(int key, int value) {
auto it = cache.find(key);
if (it == cache.end())
{
if (cache.size() == cap)
{
auto it3 = cache[lru.front().first];
cache.erase(lru.front().first);
lru.erase(it3);
}
auto i3 = lru.emplace(lru.end(), std::pair<int, int>{ key, value });
cache[key] = i3;
}
else
{
*it->second = std::pair<int, int>{ key, value };
use(it->second);
}
}
};
