LRU与LFU

【道德经·第十三章】宠辱若惊，贵大患若身。何谓宠辱若惊？宠为下，得之若惊，失之若惊，是谓宠辱若惊。何谓贵大患若身？吾所以有大患者，为吾有身，及吾无身，吾有何患！

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = m.find(key);
        if(it == m.end()) return -1;
        // 刚访问过的结点移动到链表头
        lst.splice(lst.begin(), lst, it->second);
        return m[key]->second;
    }
    
    void put(int key, int value) {
        auto it = m.find(key);
        // key已经存在，抹去
        if(it != m.end()) lst.erase(it->second);
        // 插入链表头
        lst.push_front(make_pair(key, value));
        // 建立key到list迭代器的映射
        m[key] = lst.begin();
        // 元素个数超过缓存容量大小
        if(m.size() > cap) {
            int k = lst.rbegin()->first;
            // 删除链表末尾（最近最少使用）元素
            lst.pop_back();
            m.erase(k);
        }
    }
private:
    // 缓存容量
    int cap;  
    // 链表，元素为（key，value）对
    list<pair<int, int> > lst;
    // 哈希表，key-->（key，value）迭代器
    unordered_map<int, list<pair<int, int> >::iterator> m;
};

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

460. LFU 缓存

请你为最不经常使用（LFU）缓存算法设计并实现数据结构。
实现 LFUCache 类：

LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if(m.count(key) == 0)
            return -1;
        // 将结点从freq list里摘除
        freq[m[key].second].erase(iter[key]);
        // freq自增1
        ++m[key].second;
        // 加入freq+1 list 表尾
        freq[m[key].second].push_back(key);
        // 更新迭代器位置
        iter[key] = --freq[m[key].second].end();
        // 如果minFreq list 为空，则minFreq++
        if(freq[minFreq].size() == 0) 
            ++minFreq;
        // 返回key对应的value
        return m[key].first;
    }
    
    void put(int key, int value) {
        if(cap <= 0) return;
        // 该key之前已经存在，更新value即可
        if(get(key) != -1) {
            m[key].first = value;
            return;
        }

        if(m.size() >= cap) {
            m.erase(freq[minFreq].front());
            iter.erase(freq[minFreq].front());
            freq[minFreq].pop_front();
        }

        m[key] = {value, 1};
        freq[1].push_back(key);
        iter[key] = --freq[1].end();
        minFreq = 1;
    }
private:
    // 容量，最小频率
    int cap, minFreq;
    // key-->(value, freq)
    unordered_map<int, pair<int, int> > m;
    // freq-->list of key with freq：频率为freq对应的key存在一个list里
    unordered_map<int, list<int> > freq;
    // key-->list<int>::iterator，保存key在对应freq list里的迭代器，为了实现查找O(1)
    unordered_map<int, list<int>::iterator> iter;
};

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

位我上者，灿烂星空；道德律令，在我心中。