LRU Cache

Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

// typedef list<int> LI;
// typedef pair<int, LI::iterator> PII;
// typedef unordered_map<int, PII> HIPII;
// #include <list>
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);
        // key in the cache, hit the target
        if (it != cache.end()) {
            touch(it);
        } else {
            // reach the capacity
            if (cache.size() == capacity) {
                cache.erase(used.back());
                used.pop_back();
            }
            used.push_front(key);
        }
        cache[key] = { value, used.begin() };
    }
private:
    // key, {value, iterator of list} 
    unordered_map<int, pair<int, list<int>::iterator>> cache;
    list<int> used;
    int capacity;
    // update most recent node
    // move its pos to the front
    void touch(unordered_map<int, pair<int, list<int>::iterator>>::iterator it) {
        int key = it->first;
        used.erase(it->second.second);
        used.push_front(key);
        it->second.second = used.begin();
    }
};

Similar problems

x

Tags

x