Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
LRU - DLL
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
#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); } } }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
edit mode
|
history
|
discussion