C++实现LFU算法

#include
#include
#include
using namespace std;

/*存放信息的结构体*/
class Node {
public:
    int key;
    int value;
    int frequence;//使用频率
    Node* pre;
    Node* next;
    Node() :key(0), value(0), frequence(0), pre(nullptr), next(nullptr) {};
    Node(int _key, int _value, int _frequence)
        :key(_key), value(_value), frequence(_frequence), pre(nullptr), next(nullptr) {};
};

/*双向链表*/
class DLinkedList {
private:
    //只需维护头节点和尾节点即可
    Node* head;
    Node* tail;
public:
    DLinkedList()
    {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->pre = head;
    }

    /*删除双向链表中的某个节点*/
    Node* removeNode(Node* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
        node->next = nullptr;
        node->pre = nullptr;
        return node;
    }

    bool isEmpty()
    {
        return head->next == tail;
    }

    /*将一个节点添加到链表末端*/
    void append(Node* node)
    {
        node->pre = tail->pre;
        tail->pre->next = node;
        node->next = tail;
        tail->pre = node;
    }

    /*新添加的在末尾，那么同一个访问次数下头节点位置的是最久未使用的*/
    Node* popHead()
    {
        if (head->next == tail)
            return nullptr;
        return removeNode(head->next);
    }
};

class LFUCache {
private:
    /*
    * 相当于维护了 KV表 和 KT表，可以在O(1)时间内访问到信息
    * KV表：key-value对应关系
    * KF表：key-frequence对应关系
    */
	unordered_map<int, Node*>keyToNode;

    /*
    * 维护相同访问次数的双向链表
    * KTL表：key-frequence-list
    */
    unordered_map<int, DLinkedList*>usedTimesToKey;

    int capacity;   //缓存容量大小
    int minUsedTimes;   //当前最小访问次数
public:
    LFUCache(int _capacity)
    {
        capacity = _capacity;
        minUsedTimes = 0;
    }

    int get(int key)
    {
        if (capacity == 0)
            return -1;
        if (!keyToNode.count(key))
            return -1;

        Node* node = keyToNode[key];
        int usedTimes = node->frequence;
        //将这个key从对应的KFL表中删除
        usedTimesToKey[usedTimes]->removeNode(node);
        if (usedTimes == minUsedTimes && usedTimesToKey[usedTimes]->isEmpty())
            minUsedTimes++; //更新当前最少使用次数

        //将这个节点添加到 frequence+1 的KFL表中
        putUsedTimes(node, usedTimes + 1);
        return node->value;
    }

    /*向KFL表中添加新节点*/
    void putUsedTimes(Node* node, int frequence)
    {
        /*===================================================
        * 因为已经访问一次了，所以要刷新node节点中的frequence信息
        * ===================================================
        */
        node->frequence = frequence;

        if (!usedTimesToKey.count(frequence))
            usedTimesToKey[frequence] = new DLinkedList();
        usedTimesToKey[frequence]->append(node);
    }

    void put(int key, int value)
    {
        if (capacity == 0)
            return;
        if (keyToNode.count(key))
        {
            //更新最新的value值
            keyToNode[key]->value = value;
            //刷新key对应的访问次数
            get(key);
            return;
        }
        if (keyToNode.size() == capacity)
        {
            //删除KFL中较久未使用的
            Node* removedNode = usedTimesToKey[minUsedTimes]->popHead();
            //并且删除KV表中对应的节点，必须是通过key来删除
            keyToNode.erase(removedNode->key);
            delete removedNode;
        }
        //否则就是新的node，重新添加KV值，并且frequence默认为1
        Node* node = new Node(key, value, 1);
        keyToNode[key] = node;
        minUsedTimes = 1;
        putUsedTimes(node, minUsedTimes);
    }
};