146.LRU Cache(Amazon)

http://fisherlei.blogspot.com/search?q=LRUcache

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

get(key)- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(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.

Follow up: Could you do both operations in(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

• O(1) -> HashMap + Maintaining the state for each put and get

class LRUCache {

public:
    struct cache{
        int key;
        int value;
        cache(int k, int v):key(k), value(v){

        }
    };

    LRUCache(int capacity) {
        _capacity = capacity;
    }

    int get(int key) {
        if(record.find(key) != record.end()){
            // move the cache to the front
            MovetoHead(key);

            return record[key]-> value;
        }

        return -1;
    }

    void put(int key, int value) {
        // already exists, update
        if(record.find(key) != record.end()){
            record[key]->value = value;
            MovetoHead(key);
            return;
        }

        // insert in front
        if (caches.size() >= _capacity){
            // pop the last and eliminate iterator from the record
            cout<<class(caches.back())<<endl;
            record.erase(caches.back().key);
            caches.pop_back();
        }

        cache newCache(key, value);
        caches.push_front(newCache);
        record[key] = caches.begin();

    }

 private: 
    unordered_map <int, list<cache>::iterator> record;
    list<cache> caches;
    int _capacity;

    void MovetoHead(int key){
        // move key from current location to head of the caches list
        auto updatedCache = *record[key];
        caches.erase(record[key]);
        caches.push_front(updatedCache);
        // update record info
        record[key] = caches.begin();
    }
};

/**
 * 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);
 */

Special Thanks: 水中的鱼 for the reference!