fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. using namespace std;
  4.  
  5. template <class T>
  6. struct LinkedList{
  7.     LinkedList* remove(){
  8.         if(l)   l->r = r;
  9.         if(r)   r->l = l;
  10.         return this;
  11.     }
  12.     void insert(LinkedList* &head){
  13.         r = head;
  14.         l = NULL;
  15.         if(head)    head->l = this;
  16.         head = this;
  17.     }
  18.     T x;
  19.     LinkedList* l;
  20.     LinkedList* r;
  21.     LinkedList(T X, LinkedList* L=NULL, LinkedList* R=NULL) : x(X), l(L), r(R) {}
  22. };
  23.  
  24. class LRUCache {
  25. private:
  26.     int n;
  27.     LinkedList<pair<int,int>> *head;
  28.     LinkedList<pair<int,int>> *tail;
  29.     unordered_map<int,LinkedList<pair<int,int>>*> h;
  30. public:
  31.     LRUCache(int capacity) {
  32.         n = capacity;
  33.         head = tail = new LinkedList<pair<int,int>>(make_pair(0,0));
  34.     }
  35.  
  36.     int get(int key) {
  37.         if(h.find(key)==h.end())    return -1;
  38.         if(head!=h[key])    h[key]->remove()->insert(head);
  39.         return head->x.second;
  40.     }
  41.  
  42.     void put(int key, int value) {
  43.         if(h.find(key)==h.end())    h[key] = new LinkedList<pair<int,int>>({key,value});
  44.         else    h[key]->x.second = value;
  45.         get(key);
  46.         while(h.size()>n){
  47.             key = tail->l->remove()->x.first;
  48.             delete(h[key]);
  49.             h.erase(key);
  50.         }
  51.     }
  52. };
  53. int main() {
  54. 	LRUCache cache(2);
  55. 	cache.put(1, 1);
  56. 	cache.put(2, 2);
  57. 	cout<<cache.get(1)<<endl;	// returns 1
  58. 	cache.put(3, 3);			// evicts key 2
  59. 	cout<<cache.get(2)<<endl;	// returns -1 (not found)
  60. 	cache.put(4, 4);			// evicts key 1
  61. 	cout<<cache.get(1)<<endl;	// returns -1 (not found)
  62. 	cout<<cache.get(3)<<endl;	// returns 3
  63. 	cout<<cache.get(4)<<endl;	// returns 4
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 4580KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
1
-1
-1
3
4
https://ideone.com/bCFKbb
LRU cache implementation
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!