LRU Cache实现

通过双向链表和map实现LRU Cache。

题目

参考

struct Node{
   Node* next;
   Node* prev;
   int value;
   int key;
   Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
   Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
};

class Cache{
   
   protected: 
   map<int,Node*> mp; //map the key to the node in the linked list
   int cp;  //capacity
   Node* tail; // double linked list tail pointer
   Node* head; // double linked list head pointer
   virtual void set(int, int) = 0; //set function
   virtual int get(int) = 0; //get function

};

class LRUCache : public Cache {
public:    
  LRUCache(int capacity) {
      cp = capacity;
      head = nullptr;
      tail = nullptr;
  }
  
  void set(int key, int val) override {
      auto it = mp.find(key);
      if (it != mp.end()) {
          auto node = it->second;
          node->value = val;
          if (node->prev) {
            node->prev->next = node->next;
          }
          if (node->next) {
            node->next->prev = node->prev;
          }
          if (tail == node && node->prev) {
              tail = node->prev;
          }
          node->prev = nullptr;
          if (node != head) {
            node->next = head;
          }
          head = node;
      } else {
          if (mp.size() >= cp) {
              mp.erase(tail->key);
              mp[key] = tail;
              tail->key = key;
              tail->value = val;
              head->prev = tail;
              tail->next = head;
              head = head->prev;
              tail = tail->prev;
              head->prev = nullptr;
              tail->next = nullptr;
          } else {
              auto added = new Node(nullptr, head, key, val);
              mp[key] = added;
              if (head) {
                  head->prev = added;
              }
              head = added;
              if (!tail) {
                  tail = added;
              }
          }
      }
  }
  
  int get(int key) override {
      auto it = mp.find(key);
      if (it != mp.end()) {
          return it->second->value;
      } else {
          return -1;
      }
  } 
};