LRU缓存 C++实现

LRU缓存

Least Recently Used (LRU) cache.
运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) – 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) – 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

为了让取的效率达到O(1),需要用hash。为了使得顺序存储,删除操作O(1),需要用链表。 所以需要用一个叫哈希链表的数据结构。

C++实现

键值对直接采用自带的pair实现。

list.front back 直接拿到 kv。
list.begin. back 拿到迭代器。
mp.erase(key) 根据key删除。

获取的时候,直接通过map,根据键,获取到链表的节点,并将该节点放到头部节点(先删后方),再返回该节点的value。

放入的时候。
如果有键,删除,将新的插入开头。

如果没有键,则看是否已经满了,
如果没有满,则直接放到开头。
如果满了,则删除链表尾部元素,接着放入开头。

class LRUCache {
private:
    int cap;
    list<pair<int,int>>cache;
    unordered_map<int,list<pair<int,int>>::iterator  >mp;
public:
    LRUCache(int capacity) {
        this->cap = capacity;
    }
    int get(int key){
        auto it = mp.find(key);
        if(it == mp.end()) return -1;
        pair<int,int> kv = *mp[key];
        cache.erase(mp[key]);
        cache.push_front(kv);
        mp[key] = cache.begin();
        return kv.second;
    }
    void put(int key,int value){
        auto it = mp.find(key);
        if(it != mp.end()){ // 有键
            cache.erase(mp[key]);
            cache.push_front(make_pair(key,value));
            mp[key] = cache.begin();// 更新hash
        }else{
            if(cache.size() == this->cap){// 满了
                auto last = cache.back();
                int lastKey = last.first;
                mp.erase(lastKey); // mp
                cache.pop_back();

            }
            cache.push_front(make_pair(key,value));
            mp[key] = cache.begin();
        }
    }
};

自己实现双向链表

#include <iostream>
#include <unordered_map>
using namespace std;
struct node{
    int k,v;
    node*next,*pre;
    node(int k,int v):k(k),v(v){
        next = pre = nullptr;
    }
};


class LRUCache{
public:
  int capacity;
  int size;
  unordered_map<int, node*>mp;
  node *head, *tail;
  LRUCache(int capacity):capacity(capacity){
      head = new node(-1,-1);
      tail = new node(-1,-1);
      head->next = tail;
      tail->pre = head;
      size = 0;
  }
  int get(int key){
      auto tmp = mp.find(key);
      if(tmp == mp.end()){
          return -1;
      }
      node *kv = mp[key];
      int k = kv->k;
      int v = kv->v;
      eraseNode(kv);
      pushFront(new node(k,v));
      mp[key] = head->next;
      return v;
  }
  void put(int key,int val){
      auto tmp = mp.find(key);
      if(tmp == mp.end()){
          if(size == capacity){
              node* deletedNode = tail->pre;
              deletedNode->pre->next = tail;
              tail->pre = deletedNode->pre;
              mp.erase(deletedNode->k);
              delete deletedNode;
          }else{
              size++;
          }
          node*  insertedNode = new node(key,val);
          pushFront(insertedNode);
          mp[key] = head->next;
      }else{
          node *kv = mp[key];
          int k = kv->k;
          int v = val;
          eraseNode(kv);
          pushFront(new node(k,v));
          mp[key] = head->next;
      }
  }
private:
     void eraseNode(node *tmp){
        if(!tmp) return;
        tmp->pre->next = tmp->next;
        tmp->next->pre = tmp->pre;
        delete tmp;
    }
    void pushFront(node *tmp){
        head->next->pre = tmp;
        tmp->next = head->next;
        head->next = tmp;
        tmp->pre = head;
    }
};

参考

labudadong的算法小抄。

点赞