# 146 - LRU Cache

解法一 - Hash Table + doubly linked list

這題是擴展眼界題，邊聽影片邊做，可以看：https://www.youtube.com/watch?v=q1Njd3NWvlY

class LRUCache {
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }

    int get(int key) {
        const auto it = m_.find(key);

        // Key not found, return -1
        if(it == m_.cend()) {
            return -1;
        }

        // Key found, get value and move to front
        cache_.splice(cache_.begin(), cache_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        const auto it = m_.find(key);

        // Key found
        if(it != m_.cend()) {
            it->second->second= value;
            cache_.splice(cache_.begin(), cache_, it->second);

            return;
        }

        // Key not found
        if(cache_.size() == capacity_) {
            const auto& node = cache_.back();
            m_.erase(node.first);
            cache_.pop_back();
        }

        cache_.insert(cache_.begin(), make_pair(key, value));
        m_[key] = cache_.begin();
    }

private:
    int capacity_;
    list<pair<int, int>> cache_; // Store <key, list iterator>
    unordered_map<int, list<pair<int, int>>::iterator> m_; // Store <key, value>
};

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