Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
LRU - DLL
#include<bits/stdc++.h> using namespace std; #define MAX 200005 struct node{ int key; int value; node *next, *prev; }; node nodePool[MAX]; int nodeCount; struct LRU{ node *head, *tail; }; LRU lru; map<int,node *> db; int K; int len; node *getNode(int key, int value) { node *newNode = &nodePool[nodeCount++]; newNode->key = key; newNode->value = value; newNode->prev = newNode->next = NULL; return newNode; } void push(node *cur) { if(lru.head == NULL) lru.head = lru.tail = cur; else { cur->next = lru.head; lru.head->prev = cur; lru.head = cur; } } void remove(node *cur) { if(cur==NULL) return ; if(lru.head and lru.head->key == cur->key) { lru.head = lru.head->next; if(lru.head) lru.head->prev = NULL; } if(lru.tail and lru.tail->key == cur->key) { lru.tail = lru.tail->prev; if(lru.tail) lru.tail->next = NULL; } if(cur->next) cur->next->prev = cur->prev; if(cur->prev) cur->prev->next = cur->next; cur->prev = cur->next = NULL; } // ===================================================================== void LRUCache(int cap) { db.clear(); lru.head = lru.tail = NULL; nodeCount = 0; K = cap; len = 0; } //Function to return value corresponding to the key. int GET(int key) { if(db.find(key) != db.end()) { node *curNode = db[key]; remove(curNode); push(curNode); return curNode->value; } return -1; } //Function for storing key-value pair. void SET(int key, int value) { if(db.find(key)!=db.end()) { node *curNode = db[key]; curNode->value = value; remove(curNode); push(curNode); } else { node *newNode = getNode(key,value); db[key] = newNode; if(len < K) { push(newNode); len+=1; } else { // remove tail node node *lruNode = lru.tail; remove(lruNode); db.erase(lruNode->key); // push the new node at front push(newNode); } } }
run
|
edit
|
history
|
help
0
c++ car racing game
შუალედური მეოთხე საკითხი.Mobile tariff "Cents"
My Tuple class
PyramidTransitionMatrix_recursive
sorting
mutable constexpr
Pointer to class members
PriorQ2
ammmma
hacker