LRU Cache

• Time : O(1) for each operation
• Space : O(maxSize)

#include <list>
using namespace std;

// Do not edit the class below except for the insertKeyValuePair,
// getValueFromKey, and getMostRecentKey methods. Feel free
// to add new properties and methods to the class.
class LRUCache {
	void expire() {
		while(cache.size() > maxSize) {
			auto [key, value] = cache.back();
			delete value;
			cache.pop_back();
			mp.erase(key);
		}
	}
	void update(string key, int value) {
		if(mp.count(key)) {
			auto [k, v] = *mp[key];
			delete v;
			cache.erase(mp[key]);
		}
		int *p = new int(value);
		cache.push_front({key, p});
		mp[key] = cache.begin();
	}
public:
  int maxSize;
	unordered_map<string, list<pair<string, int*>>::iterator> mp;
	list<pair<string, int*>> cache;

  LRUCache(int maxSize) { this->maxSize = maxSize > 1 ? maxSize : 1; }

  void insertKeyValuePair(string key, int value) {
    update(key, value);
		expire();
  }

  int *getValueFromKey(string key) {
    if(!mp.count(key)) return nullptr;
		auto [k, v] = *mp[key];
		update(k, *v);
    return v;
  }

  string getMostRecentKey() {
    if(cache.empty()) return "";
		
    return cache.front().first;
  }
};