Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
LRUCache
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
//Title of this code #include <iostream> #include <map> using namespace std; template <class K, class D> struct LRUNode { K key; D data; LRUNode* next; LRUNode* perv; LRUNode(K k, D d) : key(k), data(d) {} }; template <class K, class D, int maxEntries = 4> class LRUCache { map<K, LRUNode<K, D>*> lruMap; LRUNode<K, D>* head; LRUNode<K, D>* tail; int entriesNum; public: LRUCache() { entriesNum = 0; head = NULL; tail = NULL; } ~LRUCache() { LRUNode<K, D>* cur = head; LRUNode<K, D>* tmp; while (cur) { tmp = cur->next; delete cur; cur = tmp; } } void put(K key, D data) { LRUNode<K, D>* node = lruMap[key]; if (!node) { node = new LRUNode<K, D>(key, data); if (entriesNum >= maxEntries) { LRUNode<K, D>* tmp = tail; detach(tail); lruMap.erase(tmp->key); delete tmp; --entriesNum; } ++entriesNum; lruMap[key] = node; attach(node); } else { node->data = data; detach(node); attach(node); } } D get(K key) { LRUNode<K, D>* node = lruMap[key]; if (node) { //if (node != head) { detach(node); attach(node); //} return node->data; } return 0; } void print() { LRUNode<K, D>* cur = head; while (cur) { cout << cur->data << ". "; cur = cur->next; } cout << endl; } private: void detach(LRUNode<K, D>* node) { if (node == head && node->next) head = node->next; if (node == tail && node->perv) tail = node->perv; if (node->perv) { node->perv->next = node->next; } if (node->next) { node->next->perv = node->perv; } } void attach(LRUNode<K, D>* node) { if (head && head != node) { head->perv = node; node->next = head; node->perv = NULL; head = node; } else if (!head){ head = node; tail = node; } } }; int main() { LRUCache<int, int, 3> myCache; myCache.put(1,1); myCache.put(2,2); myCache.put(3,3); myCache.put(4,4); myCache.get(3); myCache.put(5,5); myCache.get(3); myCache.put(6,6); myCache.get(4); myCache.print(); }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
Compilation time: 0.44 sec, absolute running time: 0.14 sec, cpu time: 0 sec, memory peak: 3 Mb, absolute service time: 0.59 sec
edit mode
|
history
|
discussion
6. 3. 5.