LRU Cache

Description

https://leetcode.com/problems/lru-cache/description/

Solution

Time wheel

class LRUCache {
private:
    unordered_map<int, int> timer;
    unordered_map<int, int> cache;
    int maxSize;
    int time;
public:
    LRUCache(int capacity) {
        maxSize = capacity;
        time = 0;
    }
    
    int get(int key) {
        auto iter = cache.find(key);
        if (iter == cache.end() ) return -1;
        
        time += 1;
        timer[key] = time;
        return iter->second;
    }
    void evict() {
        int early = INT_MAX;
        int target = -1;
        for (auto iter = timer.begin(); iter != timer.end(); iter++) {
            if (iter->second < early) {
                early = iter->second;
                target = iter->first;
            }
        }
        cache.erase(target);
        timer.erase(target);
    }
    
    void put(int key, int value) {
        cache[key] = value;
        time += 1;
        timer[key] = time;
        if (cache.size() > maxSize) evict();
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Bidirectional Linkedlist

class LRUCache {

private:
    unordered_map<int, list<pair<int, int>>::iterator> map;
    list<pair<int, int>> lis;
    int size;
public:
    LRUCache(int capacity) {
        size = capacity;
    }
    
    int get(int key) {
        auto iter = map.find(key);
        if (iter == map.end()) return -1;
        
        auto index = iter->second;
        lis.push_front(*index);
        lis.erase(index);
        map[key] = lis.begin();
        
        return index->second;
    }
    
    void put(int key, int value) {
        
        if (map.find(key) != map.end() )
            lis.erase(map[key]);
        lis.push_front(make_pair(key, value));
        map[key] = lis.begin();
        if (lis.size() > size) {
            int deleteKey = lis.back().first;
            lis.pop_back();
            map.erase(deleteKey);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */