LFU的一种实现方法

1.数据结构

双向链表+哈希

双向链表储存pair对，key是一个hash集合(这里用unordered_set实现)，然后value就是keys集合的count。他们的次数都是相同等于count的。

然后另一个hash表，就是用来存每个key对应所在的list iterator的。

2.流程

插入

分情况讨论。

如果key不在链表中。

如果当前链表为空或者链表的表头结点的count>1。

就新建一个结点{key,1} 插入到表头。

否则直接把key放到表头结点的keys集合里。

然后更新nodes哈希表的结点。

如果key在链表中。

找到key所在结点在链表的位置cur，和它的next。

如果cur在表尾或者next对应的count>cur的count+1。

就新建一个结点，然后插入到next前面

否则把key插入到nxt的keys集合里即可。

然后从cur里删除key。

如果cur里的key为空就删除该结点。

删除

如果当前结点对应count为1，首先从nodes结点中删除该结点。

然后从链表里对应结点的key集合里删除该key

如果集合为空就删除该结点。

否则类似插入的做法，找到pre指针。

如果pre为空或者pre的count<cur的count-1

新建一个结点插入到pre位置。

否则把key插入到pre的keys集合里，更新nodes哈希表。

查询LFU

就是链表的表头结点对应的count。

查询count最大的

就是链表的表尾结点对应的count。

3.代码

class AllOne {
    list<pair<unordered_set<string>, int>> lst;
    unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> nodes;

public:
    AllOne() {}

    void inc(string key) {
        if (nodes.count(key)) {
            auto cur = nodes[key], nxt = next(cur);
            if (nxt == lst.end() || nxt->second > cur->second + 1) {
                unordered_set<string> s({key});
                nodes[key] = lst.emplace(nxt, s, cur->second + 1);
            } else {
                nxt->first.emplace(key);
                nodes[key] = nxt;
            }
            cur->first.erase(key);
            if (cur->first.empty()) {
                lst.erase(cur);
            }
        } else { // key 不在链表中
            if (lst.empty() || lst.begin()->second > 1) {
                unordered_set<string> s({key});
                lst.emplace_front(s, 1);
            } else {
                lst.begin()->first.emplace(key);
            }
            nodes[key] = lst.begin();
        }
    }

    void dec(string key) {
        auto cur = nodes[key];
        if (cur->second == 1) { // key 仅出现一次，将其移出 nodes
            nodes.erase(key);
        } else {
            auto pre = prev(cur);
            if (cur == lst.begin() || pre->second < cur->second - 1) {
                unordered_set<string> s({key});
                nodes[key] = lst.emplace(cur, s, cur->second - 1);
            } else {
                pre->first.emplace(key);
                nodes[key] = pre;
            }
        }
        cur->first.erase(key);
        if (cur->first.empty()) {
            lst.erase(cur);
        }
    }

    string getMaxKey() {
        return lst.empty() ? "" : *lst.rbegin()->first.begin();
    }

    string getMinKey() {
        return lst.empty() ? "" : *lst.begin()->first.begin();
    }
};