【C++】手撕LRU算法 - 卢小胖的开发日志

LRU

LRU(Least Recently Used) 即最近最少使用，属于典型的内存淘汰机制。

该算法需要达到两个目的：

可以轻易的更新最新的访问数据。
轻易的找出最近最少未使用的数据。

所以要用到哈希表+双向链表实现。利用map，获取key对应的value是O(1)，利用双向链表，实现新增和删除都是O(1)。

版本1：自己实现循环链表存储，没有用API

/********************不用API的版本*************************/
/********************简单说一下思路*************************/
//1.首先hash表用的是unordered_map来实现，用来查找key对应的node节点，所以hash表应该是[key,node]形式存储
//2.LRUCache这个类实现双向链表的添加，删除，更新和遍历
//3.同时这个类还要实现get和put两个功能
//4.我这里用的是循环双向链表，因此查找链表尾端的元素为O(1)，正常的双向链表是O(n)
//总结：最重要的就是hash表中的key对应的不是int而是一个node节点，这个要记住
#include<unordered_map>
#include<iostream>
struct Node{
    int key;
    int value;
    Node* pre;
    Node* next;
    Node(){}
    Node(int k, int v):key(k), value(v), pre(nullptr), next(nullptr){}
};

class LRUCache{
private:
    //通过key可以找到位于链表中的节点
    std::unordered_map<int, Node*> hash;
    int capacity;
    Node* head_node;
public:
    LRUCache(int cap){
        capacity = cap;
        head_node = new Node();
        //初始化dummy_Node,next和pre都指向自己
        head_node->next = head_node->pre = head_node;
    }
    //将新来的插入双向链表头部
    void add_Node(Node* n);
    //将某个节点拿出来重新插入头部
    void update_Node(Node* n);
    //移除链表中最后一个（最久未使用）
    void pop_back();
    //输出LRU结构
    void show();
    int get(int key);
    void put(int key, int value);
};

//注意，该节点可能是新节点，也可能是已经存在的有重新入链表的节点
void LRUCache::add_Node(Node* n){
    //表示当前节点n就是dummy的next节点，不用加入
    if(n->pre == head_node){
        return;
    }
    //将节点n插入head_node后面
    n->pre = head_node;
    n->next = head_node->next;
    head_node->next->pre = n;
    head_node->next = n;
}

void LRUCache::update_Node(Node* n){
    //表示当前节点n就是dummy的next节点，不用断掉
    if(n->pre == head_node){
        return;
    }
    n->next->pre = n->pre;
    n->pre->next = n->next;
    add_Node(n);
}

//弹出链表的最后一个，由于是循环链表，就是head_node->pre
void LRUCache::pop_back(){
    Node* tmp = head_node->pre;
    head_node->pre = tmp->pre;
    tmp->pre->next = head_node;
    //删除unordered_map中的key
    hash.erase(tmp->key);
}

void LRUCache::show(){
    //链表中没有节点，退出
    if(head_node->next = head_node){
        return;
    }
    Node* tmp = head_node->next;
    while(tmp->next != head_node){
        std::cout<<"key:"<<tmp->key<<",vlaue:"<<tmp->value<<std::endl;
    }
}
int LRUCache::get(int key){
    auto it = hash.find(key);
    if(it == hash.end()){
        std::cout<<"there is no key"<<std::endl;
        return -1;
    }
    //取出key对应的node节点
    Node* node = it->second;
    update_Node(node);
    return node->value;

}
void LRUCache::put(int key, int value){
    auto it = hash.find(key);
    if(it == hash.end()){
        Node* node = new Node(key, value);
        add_Node(node);
        hash.insert({key, node});
        if(hash.size() > capacity){
            
            pop_back();
        }
    }else{
        it->second->value = value;
        update_Node(it->second);
    }
}

版本2：使用deque

#include <iostream>
#include <deque>
#include <unordered_map>

class LRU
{
private:
    int size;
    //为什么使用deque
    std::deque<std::pair<int,int>> _deque;
    std::unordered_map<int,std::deque<std::pair<int,int>>::iterator> map;

public:
    LRU(int cap) : size(cap) {}

    int get(int key);

    void put(int key, int value);

    void print()
    {
        for (auto& item : _deque) {
            std::cout << item.first << "-" << item.second << "\t";
        }
        std::cout << std::endl;
    }
};

int LRU::get(int key) {
    //if (map.count(key) > 0)
    if (map.find(key) == map.end())
    {
        std::cout << "key not exist!" << std::endl;
        return -1;
    }
    auto temp = *map[key];
    _deque.erase(map[key]);
    //注意这里是push_front
    _deque.push_front(temp);
    map[key] = _deque.begin();
    return temp.second;
}

void LRU::put(int key, int value) {
    if (map.find(key) == map.end())
    {
        //满了，删除最后一个
        if (size == map.size())
        {
            auto tail = _deque.back();
            map.erase(tail.first);
            _deque.pop_back();
        }
        //注意这里是push_front
        _deque.push_front({key,value});
        map[key] = _deque.begin();
    }
    else
    {
        //更新值
        _deque.erase(map[key]);
        _deque.push_front({key,value});
        map[key] = _deque.begin();
    }
}

测试：


int main()
{
    LRU lru(5);
    for (int i = 0; i < 5; ++i) {
        lru.put(i,i);
    }
    lru.print();

    lru.put(2,2);
    lru.print();


    lru.put(8,8);
    lru.put(10,10);
    lru.print();

}


4-4     3-3     2-2     1-1     0-0
2-2     4-4     3-3     1-1     0-0
10-10   8-8     2-2     4-4     3-3

实现三：加入模板

#include <iostream>
#include <unordered_map>
#include <iterator>

template<typename T>
struct Node
{
    int key;
    T* value;
    Node* pre;
    Node* next;
    Node() : pre(nullptr), next(nullptr), key(0), value(nullptr) { }
    Node(int key, T* value) : pre(nullptr), next(nullptr), key(key), value(value) { }
};

template<typename T>
class LruCache
{
private:
    Node<T>* head;
    Node<T>* tail;
    int size;
    std::unordered_map<int,Node<T>*> map;

public:
    LruCache(int size) : size(size) {}

    T* get(int key)
    {
        if (map.count(key))
        {
            Node<T>* node = map.find(key);
            remove(node);
            setHead(node);
            return node->value;
        }
        else
        {
            return nullptr;
        }
    }

    void put(int key, T* value)
    {
        if (map.count(key) > 0)
        {
            Node<T>* node = map[key];
            //更新value的值
            node->value = value;
            //更新Node位置
            remove(node);
            setHead(node);
        }
        else
        {
            //原来的map中没有这个数据，新构建一个
            Node<T>* node = new Node<T>(key,value);

            //map满了，删除不常用的元素
            if (size == map.size())
            {
//                auto it = map.find(tail->key);
//                remove(tail);
//                map.erase(it);
                map.erase(tail->key);
                remove(tail);
            }

            //更新map
            setHead(node);
            map[key] = node;
        }
    }


    //删除当前元素
    void remove(Node<T>* node)
    {
        if (node == head)
        {
            head = head->next;
        }
        else if (node == tail)
        {
            tail = tail->pre;
        }
        else
        {
            node->pre->next = node->next;
            node->next->pre = node->pre;

//            node->pre = nullptr;
//            node->next = nullptr;
//            delete node;
        }
    }

    //设置当前元素为头节点
    void setHead(Node<T>* node)
    {
        node->next = head;
        if (head != nullptr)
        {
            head->pre = node;
        }
        head = node;
        if (tail == nullptr)
        {
            tail = head;
        }
    }

//    ~LruCache()
//    {
//        while (head != nullptr)
//        {
//            auto next = head->next;
//            delete head;
//            head = next;
//        }
//    }

    void print()
    {
        auto node = head;
        while (node != nullptr && node->value != nullptr)
        {
            std::cout  << node->key  << " -  " << *(node->value) << "\t\t";
            node = node->next;
        }
        std::cout << std::endl;
    }
};

测试：

int main()
{
    LruCache<std::string> lruCache(5);
    lruCache.put(1,new std::string("AA"));
    lruCache.put(2,new std::string("BB"));
    lruCache.put(3,new std::string("CC"));
    lruCache.put(4,new std::string("DD"));
    lruCache.put(5,new std::string("EE"));
    lruCache.print();

    lruCache.put(4,new std::string("DD"));
    lruCache.put(1,new std::string("AA"));
    lruCache.put(4,new std::string("DD"));
    lruCache.print();


    lruCache.put(6,new std::string("FFFF"));
    lruCache.put(7,new std::string("abc"));
    lruCache.print();

    return 0;
}

5 -  EE         4 -  DD         3 -  CC         2 -  BB         1 -  AA
4 -  DD         1 -  AA         5 -  EE         3 -  CC         2 -  BB
7 -  abc                6 -  FFFF               4 -  DD         1 -  AA        5 -  EE          3 -  CC         2 -  BB

这个模板类应该是有问题的，要考虑到指针的释放时机，拷贝构造移动构造赋值等情况，这里实现的比较简单。

LRU

版本1：自己实现循环链表存储，没有用API

版本2：使用deque

实现三：加入模板

特色标签