fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class LRUCache {
  5. public:
  6.     int capacity;
  7.     unordered_map<int, list<pair<int, int>>::iterator> map;
  8.     list<pair<int, int>> values;
  9.     LRUCache(int capacity) {
  10.         this->capacity = capacity;
  11.     }
  12.  
  13.     int get(int key) {
  14.         if(map.find(key) == map.end()) {
  15.             return -1;
  16.         }
  17.  
  18.         else {
  19.            list<pair<int, int>>::iterator itr = map[key];
  20.            int key = itr->first;
  21.            int value = itr->second;
  22.            values.erase(itr);
  23.            values.push_front({key, value});
  24.            map[key] = values.begin();
  25.            return value;
  26.         }
  27.     }
  28.  
  29.     void put(int key, int value) {
  30.         if(map.find(key) == map.end()) {
  31.             if(map.size() == this->capacity) {
  32.                 // delete oldest
  33.                 list<pair<int, int>>::iterator itr = values.end();
  34.                 itr--;
  35.                 map.erase(itr->first);
  36.                 values.erase(itr);
  37.                 values.push_front({key, value});
  38.                 map[key] = values.begin();
  39.             }
  40.  
  41.             else {
  42.                 // only insertion
  43.                 values.push_front({key, value});
  44.                 map[key] = values.begin();
  45.             }
  46.  
  47.         }
  48.  
  49.         else {
  50.             // no change in capacity, only value changes
  51.             list<pair<int, int>>::iterator itr = map[key];
  52.             int key = itr->first;
  53.             values.erase(itr);
  54.             values.push_front({key, value});
  55.             map[key] = values.begin();
  56.  
  57.         }
  58.     }
  59. };
  60.  
  61.  
  62. int main() {
  63.  
  64. 	LRUCache* lRUCache = new LRUCache(2);
  65. 	lRUCache->put(1, 1); // cache is {1=1}
  66. 	lRUCache->put(2, 2); // cache is {1=1, 2=2}
  67. 	cout << lRUCache->get(1) << endl;    // return 1
  68.  
  69. 	return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/OadjNd
language:
C++ (gcc 8.3)
created:
43 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!