[LeetCode] LRU Cache

The basic idea is to store the key-value pair in some container. In the following code, we make three type definitions:

typedef list<int> LI;
typedef pair<int, LI::iterator> PII;
typedef unordered_map<int, PII> HIPII;

HIPII is the ultimate type for the container. It is essentially an unordered_map, using key as its key and a pair as its value. The first element of the pair is the value and the second element of it is the iterator of the key in a list (front elements are more recently used).  So each element in the HIPII container is like a {int key, {int value, iterator}}.

Now the implementation of get and set is relatively straightforward: each time we access a key, touch it (making it at the beginning of the list) and then get or set its value. If the container has met its size and we need add a new key, just remove the key corresponding to the last element of list (least recently used).

The code is as follows.

class LRUCache{
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        touch(it);
        return it -> second.first;
    }
    
    void set(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) touch(it);
        else {
            if (cache.size() == _capacity) {
                cache.erase(used.back());
                used.pop_back();
            }
            used.push_front(key);
        }
        cache[key] = {value, used.begin()};
    }
private:
    typedef list<int> LI;
    typedef pair<int, LI::iterator> LII;
    typedef unordered_map<int, LII> HIPII;
    
    int _capacity;
    LI used;
    HIPII cache;
    
    void touch(HIPII::iterator it) {
        int key = it -> first;
        used.erase(it -> second.second);
        used.push_front(key);
        it -> second.second = used.begin();
    }
};