fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Node {
  6.     string key;
  7.     string value;
  8.     Node* prev;
  9.     Node* next;
  10.  
  11.     Node(const string &k, const string &v) 
  12.     {
  13.         key = k;
  14.         value = v;
  15.         prev = nullptr;
  16.         next = nullptr;
  17.     }
  18. };
  19.  
  20. class LRUCache 
  21. {
  22. private:
  23.     int capacity;
  24.     unordered_map<string, Node*> cacheMap;
  25.     Node* head;
  26.     Node* tail;
  27.  
  28.     void moveToHead(Node* node) 
  29.     {
  30.         if (node == head) return;
  31.  
  32.         if (node->prev) node->prev->next = node->next;
  33.  
  34.         if (node->next) node->next->prev = node->prev;
  35.  
  36.         if (node == tail) tail = node->prev;
  37.  
  38.         node->next = head;
  39.         node->prev = nullptr;
  40.         if (head) head->prev = node;
  41.         head = node;
  42.  
  43.         if (!tail) tail = head;
  44.     }
  45.  
  46. public:
  47.     LRUCache(int cap)
  48.     {
  49.         capacity = cap;
  50.         head = nullptr;
  51.         tail = nullptr;
  52.     }
  53.  
  54.     string get(const string &key) 
  55.     {
  56.         if (cacheMap.count(key)) 
  57.         {
  58.             Node* node = cacheMap[key];
  59.             moveToHead(node);
  60.             cout << "Get: " << key << " -> " << node->value << endl;
  61.             return node->value;
  62.         }
  63.         cout << "Get: " << key << " -> Not found" << endl;
  64.         return "";
  65.     }
  66.  
  67.     void put(const string &key, const string &value) 
  68.     {
  69.         if (cacheMap.count(key)) 
  70.         {
  71.             Node* node = cacheMap[key];
  72.             node->value = value;
  73.             moveToHead(node);
  74.             cout << "Put (update): " << key << " = " << value << endl;
  75.         } 
  76.         else 
  77.         {
  78.             Node* newNode = new Node(key, value);
  79.             cacheMap[key] = newNode;
  80.  
  81.             if (head == nullptr) head = tail = newNode;
  82.             else 
  83.             {
  84.                 newNode->next = head;
  85.                 head->prev = newNode;
  86.                 head = newNode;
  87.             }
  88.             cout << "Put: " << key << " = " << value << endl;
  89.  
  90.             if (cacheMap.size() > capacity) 
  91.             {
  92.                 if (tail != nullptr) 
  93.                 {
  94.                     string evictedKey = tail->key; // Lưu trữ key trước khi xóa
  95.                     cacheMap.erase(tail->key);
  96.                     Node* temp = tail;
  97.                     tail = tail->prev;
  98.                     if (tail) {
  99.                         tail->next = nullptr;
  100.                     } else {
  101.                         head = nullptr;
  102.                     }
  103.                     delete temp;
  104.                     cout << "Evict: " << evictedKey << endl;
  105.                 } 
  106.                 else 
  107.                 {
  108.                     // Trường hợp cache có capacity 1 và đầy
  109.                     string evictedKey = head->key;
  110.                     cacheMap.erase(head->key);
  111.                     delete head;
  112.                     head = tail = nullptr;
  113.                     cout << "Evict: " << evictedKey << endl;
  114.                 }
  115.             }
  116.         }
  117.     }
  118.  
  119.     void printCache() const 
  120.     {
  121.         cout << "Cache: ";
  122.         Node* current = head;
  123.         while (current) {
  124.             cout << "(" << current->key << ":" << current->value << ") ";
  125.             current = current->next;
  126.         }
  127.         cout << endl;
  128.     }
  129.  
  130.     ~LRUCache() 
  131.     {
  132.         Node* current = head;
  133.         while (current) {
  134.             Node* next = current->next;
  135.             delete current;
  136.             current = next;
  137.         }
  138.     }
  139. };
  140.  
  141. int main() {
  142.     LRUCache lruCache(3);
  143.  
  144.     lruCache.put("1", "one");
  145.     lruCache.printCache();
  146.  
  147.     lruCache.put("2", "two");
  148.     lruCache.printCache();
  149.  
  150.     lruCache.put("3", "three");
  151.     lruCache.printCache();
  152.  
  153.     lruCache.get("2");
  154.     lruCache.printCache();
  155.  
  156.     lruCache.put("4", "four");
  157.     lruCache.printCache();
  158.  
  159.     lruCache.get("1");
  160.     lruCache.printCache();
  161.  
  162.     lruCache.get("3");
  163.     lruCache.printCache();
  164.  
  165.     lruCache.put("5", "five");
  166.     lruCache.printCache();
  167.  
  168.     LRUCache lruCacheSingle(1);
  169.     lruCacheSingle.put("a", "1");
  170.     lruCacheSingle.printCache();
  171.     lruCacheSingle.put("b", "2");
  172.     lruCacheSingle.printCache();
  173.     lruCacheSingle.get("b");
  174.     lruCacheSingle.printCache();
  175.  
  176.     return 0;
  177. }
Success #stdin #stdout 0.01s 5240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Put: 1 = one
Cache: (1:one) 
Put: 2 = two
Cache: (2:two) (1:one) 
Put: 3 = three
Cache: (3:three) (2:two) (1:one) 
Get: 2 -> two
Cache: (2:two) (3:three) (1:one) 
Put: 4 = four
Evict: 1
Cache: (4:four) (2:two) (3:three) 
Get: 1 -> Not found
Cache: (4:four) (2:two) (3:three) 
Get: 3 -> three
Cache: (3:three) (4:four) (2:two) 
Put: 5 = five
Evict: 2
Cache: (5:five) (3:three) (4:four) 
Put: a = 1
Cache: (a:1) 
Put: b = 2
Evict: a
Cache: (b:2) 
Get: b -> 2
Cache: (b:2)
https://ideone.com/3DKiki
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!