leetcode 146. LRU Cache 、460. LFU Cache

LRU算法是首先淘汰最长时间未被使用的页面，而LFU是先淘汰一定时间内被访问次数最少的页面，如果存在使用频度相同的多个项目，则移除最近最少使用（Least Recently Used）的项目。

LFU在频度相同的时候与LRU类似。

146. LRU Cache

1.stl中list是双向链表，slist才是单向链表。

rbegin():返回尾元素的逆向迭代器指针

end():返回尾元素之后位置的迭代器指针

https://www.cnblogs.com/Kobe10/p/5780095.html

2.使用hash是让查询的时间复杂度为O(1)，使用双向链表，是cache里面数值移动的时间复杂度为O(1)。如果采用数组，移动的时间复杂度为O(n)，因为你需要将第i个放到首位，然后原本的前i-1个都需要逐个向后移动一个。队列的操作也是如此，你需要先弹出前i-1同时都弹到队尾，然后取出当前的i，然后把原本i后面剩下的也都弹出放到队尾，再把原本的i放到头部。

3.另外一个非常关键的降低时间复杂度的方法是在hash中保存那个key在链表中对应的指针, 我们知道链表要查找一个结点的时间复杂度是O(n), 所以当我们需要移动一个结点到链表首部的时候, 如果直接在链表中查询那个key所对于的结点, 然后再移动, 这样时间复杂度将会是O(n), 而一个很好的改进方法是在hash表中存储那个key在链表中结点的指针, 这样就可以在O(1)的时间内移动结点到链表首部.
4.unordered_map: size(): 返回有效元素个数

　　　　　　　　　find()：通过给定主键查找元素,没找到：返回unordered_map::end

　　　　　　　　　find返回的是一个迭代器，这个迭代器用->first、->second分别访问key和value

count()：返回匹配给定主键的元素的个数，也就是同一个key，对应多少个value

　　　　　　　　　unordered_map可以通过主键来访问，返回是value值。比如m[1] = 1。find返回的则是迭代器，且迭代器指向的是键值对，first对应键，second对应值。

　　　　　　　　　rbegin是最后一个元素

　　　　　　　　 m.find(key) != m.end()就不在容器中

　　　　　　　　　erase()可以删除指针，也可以删除key

5.双向链表list的splice函数，void splice (iterator position, list& x, iterator i); //将列表x中迭代器 i 指向的元素移到当前list的position指向的位置处，由于i指向的元素从列表x中被移除，所以迭代器 i 此时是invalid的；position是当前列表的迭代器，i是列表x的迭代器。时间复杂度为0(1)

list：pop_back删除最后一个元素

push_front在前面加入

6.pair、make_pair: std::pair主要的作用是将两个数据组合成一个数据，两个数据可以是同一类型或者不同类型,->first、->second用于访问pair中的第一个和第二个元素

　　　　　　　　　 make_pair:无需写出型别，就可以生成一个pair对象

　　　　　　　　　　　　　　　例： std::make_pair(42, '@');

　　　　　　　　　　　　　　　　　而不必费力写成：
　　　　　　　　　　　　　　　　　 std::pair<int, char>(42, '@')

7.auto:可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型

8.迭代器：是一种检查容器内元素并遍历元素的数据类型。C++更趋向于使用迭代器而不是下标操作，因为标准库为每一种标准容器（如vector）定义了一种迭代器类型，而只有少数容器（如vector）支持下标操作访问容器元素。

9. l.splice(l.begin(), l, it->second);这一行将l的位置移动了，主要是先删除原先的位置，再放到头部。我以为那个迭代器会失效，认为这个地方应该更新hash里面的迭代器，所以在后面一行增加了m[key] = l.begin();。但是经过测试没有失效

测试的代码如下：

int main(){
    LRUCache debug(3);
    // cout << debug.cap << endl;
    debug.put(1,1);
    debug.put(2,2);
    debug.put(3,3);
    cout << debug.l.rbegin()->first << endl;
    cout << debug.get(1) << endl;
    cout << debug.l.rbegin()->first << endl;
}

测试的结果：

在测试的时候，自己对构造函数的初始化不是很了解，所以最开始的测试代码错误写成如下：

int main(){
    LRUCache debug;
    debug.LRUCache(3);
}

正确代码：

class LRUCache{
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        l.splice(l.begin(), l, it->second);
        //m[key] = l.begin(); 自己以为迭代器会失效，但是没有
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = m.find(key);
        if (it != m.end()) l.erase(it->second);
        l.push_front(make_pair(key, value));
        m[key] = l.begin();
        if (m.size() > cap) {
            int k = l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }
    
private:
    int cap;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};

https://www.cnblogs.com/lalalabi/p/5060210.html

http://www.cnblogs.com/grandyang/p/4587511.html

https://blog.csdn.net/qq508618087/article/details/50995188

460. LFU Cache

https://www.cnblogs.com/grandyang/p/6258459.html

因为需要判断key出现的频率，所以必须存储不同的频率。并且同一个频率，可能有不同的key，也就是说freq至少是一个unordered_map<int,vector<int>>的形式。但是你需要删除，vector删除不是O(1)的时间复杂度，双向链表list是，所以是unordered_map<int,list<int>>。要删除，这就和lru类似了，你需要存储key在list中的位置，直接找到这个位置，所以还需要unordered_map<int,list<int>::iterator>。对应的还需要存储key、value，并且需要找到每个key对应的频率，所以需要存储vector<key,pair<value,freq>>。

错误代码：

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = m.find(key);
        if(it == m.end())
            return -1;
        int fre = it->second->second;
        freq[fre].erase(iter[key]);
        fre++;
        freq[fre].push_front(key);
        iter[key] = freq[fre].begin();
        it->second->second++;
        if(freq[min_freq].size() == 0)
            min_freq++;
        return it->second->first;
    }
    
    void put(int key, int value) {
        auto it = m.find(key);
        if(get(key) != -1){
            m[key]->first = value;
            return;
        }
        if(m.size() > cap){
            int k = freq[min_freq].rbegin();
            freq.pop_back();
            m.erase(k);
            iter.erase(k);
        }
        m[key] = {value,1};
        freq[1].push_front(key);
        iter[key] = freq[1].begin();
        min_freq = 1;
    }

private:
    int cap,min_freq;
    unordered_map<int,pair<int,int>> m;
    unordered_map<int,list<int>> freq;    
    unordered_map<int,list<int>::iterator> iter;
};

m<key,pair<value,freq>>

freq<freq,list<key>>

iter<key,freq的list中的位置>

正确代码：

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = m.find(key);
        if(it == m.end())
            return -1;
        int fre = it->second.second;
        freq[fre].erase(iter[key]);
        fre++;
        freq[fre].push_front(key);
        iter[key] = freq[fre].begin();
        it->second.second++;
        if(freq[min_freq].size() == 0)
            min_freq++;
        return it->second.first;
    }
    
    void put(int key, int value) {
        if(cap <= 0)
            return;
        if(get(key) != -1){
            m[key].first = value;
            return;
        }
        if(m.size() >= cap){
            int k = *freq[min_freq].rbegin();
            freq[min_freq].pop_back();
            m.erase(k);
            iter.erase(k);
        }
        m[key] = {value,1};
        freq[1].push_front(key);
        iter[key] = freq[1].begin();
        min_freq = 1;
    }

private:
    int cap,min_freq;
    unordered_map<int,pair<int,int>> m;
    unordered_map<int,list<int>> freq;    
    unordered_map<int,list<int>::iterator> iter;
};

之间写的一个代码：

hash:存储的key、value、freq

freq:存储的freq、key，也就是说出现1次的所有key在一起，用list连接

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = hash.find(key);
        if(it == hash.end())
            return -1;                              这段代码以下处理的都是已有key的情况

        freq[hash[key].second].erase(iter[key]);    如果这个key已经有了，那次数就要加1。所以必须把freq里面的对应次数的key先删除，然后更新hash里key对应的次数，
        ++hash[key].second;                         同时在freq中将这个key连接次数加1的地方
        freq[hash[key].second].push_back(key);
        iter[key] = --freq[hash[key].second].end(); 因为这个key在freq中变换了位置，那对应的迭代器地址也应该改变，是push_back进去的，所以尾地址-1就好了
        if(freq[min_freq].size() == 0)              代码走到这一步，一定是有key存在的。如果min_freq没有了值，证明就是
            ++min_freq;
        return hash[key].first;
    }
    
    void put(int key, int value) {
        if(cap <= 0)
            return;
        if(get(key) != -1){                          注意调用的是 get(key)，不是find
            hash[key].first = value;                 如果这个key已经存在，就不用考虑容量的问题，直接更新value就好了，因为不用新添加
            return;
        }
        if(hash.size() >= cap){
            hash.erase(freq[min_freq].front());      删除出现次数最少的中最久未出现的，list中越新出现的从后push进去
            iter.erase(freq[min_freq].front());      为什么要删除迭代器？？？
            freq[min_freq].pop_front();
        }
        hash[key] = {value,1};                       对出现一次的key进行添加
        freq[1].push_back(key);
        iter[key] = --freq[1].end();
        min_freq = 1;
    }
    int cap,min_freq;
    unordered_map<int,pair<int,int>> hash;           <key,pair<value,freq>>
    unordered_map<int,list<int>> freq;　　　　　　　　　<freq,list<key>>
    unordered_map<int,list<int>::iterator> iter;     <freq,list<key>::iterator>
};