{"id":668,"date":"2021-12-04T15:38:58","date_gmt":"2021-12-04T07:38:58","guid":{"rendered":"https:\/\/blog.cauchyschwarz.com\/?p=668"},"modified":"2021-12-04T22:19:36","modified_gmt":"2021-12-04T14:19:36","slug":"lru-cache%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/blog.cauchyschwarz.com\/?p=668","title":{"rendered":"LRU Cache\u5b9e\u73b0"},"content":{"rendered":"\n

\u901a\u8fc7\u53cc\u5411\u94fe\u8868\u548cmap\u5b9e\u73b0LRU Cache\u3002<\/p>\n\n\n\n

\u9898\u76ee<\/a><\/p>\n\n\n\n

\u53c2\u8003<\/a><\/p>\n\n\n\n

struct Node{\n   Node* next;\n   Node* prev;\n   int value;\n   int key;\n   Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};\n   Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};\n};\n\nclass Cache{\n   \n   protected: \n   map<int,Node*> mp; \/\/map the key to the node in the linked list\n   int cp;  \/\/capacity\n   Node* tail; \/\/ double linked list tail pointer\n   Node* head; \/\/ double linked list head pointer\n   virtual void set(int, int) = 0; \/\/set function\n   virtual int get(int) = 0; \/\/get function\n\n};\n\nclass LRUCache : public Cache {\npublic:    \n  LRUCache(int capacity) {\n      cp = capacity;\n      head = nullptr;\n      tail = nullptr;\n  }\n  \n  void set(int key, int val) override {\n      auto it = mp.find(key);\n      if (it != mp.end()) {\n          auto node = it->second;\n          node->value = val;\n          if (node->prev) {\n            node->prev->next = node->next;\n          }\n          if (node->next) {\n            node->next->prev = node->prev;\n          }\n          if (tail == node && node->prev) {\n              tail = node->prev;\n          }\n          node->prev = nullptr;\n          if (node != head) {\n            node->next = head;\n          }\n          head = node;\n      } else {\n          if (mp.size() >= cp) {\n              mp.erase(tail->key);\n              mp[key] = tail;\n              tail->key = key;\n              tail->value = val;\n              head->prev = tail;\n              tail->next = head;\n              head = head->prev;\n              tail = tail->prev;\n              head->prev = nullptr;\n              tail->next = nullptr;\n          } else {\n              auto added = new Node(nullptr, head, key, val);\n              mp[key] = added;\n              if (head) {\n                  head->prev = added;\n              }\n              head = added;\n              if (!tail) {\n                  tail = added;\n              }\n          }\n      }\n  }\n  \n  int get(int key) override {\n      auto it = mp.find(key);\n      if (it != mp.end()) {\n          return it->second->value;\n      } else {\n          return -1;\n      }\n  } \n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u901a\u8fc7\u53cc\u5411\u94fe\u8868\u548cmap\u5b9e\u73b0LRU Cache\u3002 \u9898\u76ee \u53c2\u8003<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[26,65],"class_list":["post-668","post","type-post","status-publish","format-standard","hentry","category-10","tag-algorithm","tag-lru"],"_links":{"self":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/668","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=668"}],"version-history":[{"count":5,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/668\/revisions"}],"predecessor-version":[{"id":677,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/668\/revisions\/677"}],"wp:attachment":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}