C++ solution with times map


#1

size_t lru_max_size;
map<int, pair<int, int>> lru;
map<int, int> time_map; //time to key map;
int lru_count;

LRUCache::LRUCache(int capacity) {
lru_max_size = capacity;
lru.clear();
lru_count = 0;
}

int LRUCache::get(int key) {
auto itr = lru.find(key);
if (itr != lru.end())
{
//TODO update times
time_map.erase(itr->second.second);
time_map[lru_count] = key;
itr->second.second = lru_count;
++lru_count;
return itr->second.first;
}
return -1;
}

void LRUCache::set(int key, int value) {
int prevVal = get(key);
if(prevVal != -1) //key existed
{
lru[key].first = value;
}
else //new key
{
if (lru.size() == lru_max_size)
{
int key_to_erase = time_map.begin()->second;
time_map.erase(time_map.begin());
lru.erase(key_to_erase);
}
lru[key] = make_pair(value, lru_count);
time_map[lru_count] = key;
++lru_count;
}
}