设计LRU缓存结构分析

三个核心数据结构设计或选择

1. 缓存cache明显属于key-value的数据结构，要让访问性能高，可以考虑hash表，所以可以选择c++中的unordered_map（当然unordered_map实现比较复杂，在规模大时才是hash，这里不必细纠）。
2. 可以维护一个按照最近使用时间排序的链表list，元素为记录key，当set操作超cache大小k，需要删除cache中的记录时，直接找到list的头结点（要删除记录的key）来操作。
3. 在进行get或set操作时，将操作的key重新排在list的末尾。要追求性，这就要求要很快找到list中key所在位置，一般list明显没有这个功能。可以单独使用一个unordered_map来保存每个key对应的list中的位置。

算法实现就是维护好这三个数据结构

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    void set(int key, int val, 
            unordered_map<int, int> &cache, 
            list<int> &lst, 
            unordered_map<int, list<int>::iterator> &lstMap,
            int k)
    {
        auto it = cache.find(key);
        if (it == cache.end())
        {
            if ((int)cache.size() >= k)
            {
                int deleteKey = lst.front();
                lst.erase(lst.begin());
                lstMap.erase(deleteKey);
                cache.erase(deleteKey);
            }
        }
        else
        {         
            lst.erase(lstMap[key]);
        }
           
        cache[key] = val;
        lst.push_back(key);
        lstMap[key] = prev(lst.end());
    }

    int get(int key, int val, 
            unordered_map<int, int> &cache, 
            list<int> &lst, 
            unordered_map<int, list<int>::iterator> &lstMap)
    {
        
        auto it = cache.find(key);
        if (it == cache.end())
        {
            return -1;
        }

        lst.erase(lstMap[key]);
        lst.push_back(key);
        lstMap[key] = prev(lst.end());

        return it->second;
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> ret;
        unordered_map<int, int> cache;
        list<int> lst;  // latest used push into last;
        unordered_map<int, list<int>::iterator> lstMap;
        for (int i = 0; i < (int)operators.size(); i++)
        {
            if (operators[i][0] == 1)
            {
                set(operators[i][1], operators[i][2], cache, lst, lstMap, k);                
            }
            else
            {
                ret.push_back(get(operators[i][1], operators[i][2], cache, lst, lstMap));
            }
        }

        return ret;
    }
};