include
include
class Cache { public: virtual void set(int key, int value) = 0; virtual int get(int key) = 0; };
class LRUCache : public Cache { private: struct Node { int key; int value; Node* prev; Node* next; };
std::unordered_map<int, Node*> mp; int cp; Node* head; Node* tail;public: LRUCache(int capacity) { cp = capacity; head = nullptr; tail = nullptr; }
void set(int key, int value) { if (mp.find(key) != mp.end()) { // Update existing key and move it to the front. Node* node = mp[key]; node->value = value; moveToFront(node); } else { // Create a new node and insert it at the front. Node* newNode = new Node{key, value, nullptr, nullptr}; if (mp.size() == cp) { // Remove the least recently used item (tail). mp.erase(tail->key); removeTail(); } mp[key] = newNode; addToFront(newNode); } } int get(int key) { if (mp.find(key) != mp.end()) { // Move the accessed item to the front and return its value. Node* node = mp[key]; moveToFront(node); return node->value; } return -1; // Cache miss. }private: void moveToFront(Node* node) { if (node == head) { return; // Already at the front. } removeNode(node); addToFront(node); }
void addToFront(Node* node) { node->next = head; node->prev = nullptr; if (head) { head->prev = node; } head = node; if (!tail) { tail = node; } } void removeNode(Node* node) { if (node->prev) { node->prev->next = node->next; } else { head = node->next; } if (node->next) { node->next->prev = node->prev; } else { tail = node->prev; } } void removeTail() { if (!tail) { return; } if (tail->prev) { tail->prev->next = nullptr; } else { head = nullptr; } delete tail; tail = nullptr; }};
int main() { int n, capacity; std::cin >> n >> capacity;
LRUCache lruCache(capacity); for (int i = 0; i < n; i++) { std::string command; std::cin >> command; if (command == "set") { int key, value; std::cin >> key >> value; lruCache.set(key, value); } else if (command == "get") { int key; std::cin >> key; std::cout << lruCache.get(key) << std::endl; } } return 0;}
Here's a version without all the comments. Hope this helps.
class LRUCache : public Cache{ private: void update_usage(int k){ auto node = mp[k]; if(node == head || node == tail) return; node->prev->next = node->next; node->next->prev = node->prev; node->prev = nullptr; node->next = head; head->prev = node; head = node; } public: void set(int k, int v) override { if(mp.find(k) != mp.end()){ mp[k]->value = v; update_usage(k); } else{ Node* new_node = new Node(k, v); if(head == nullptr){ head = new_node; tail = new_node; mp[k] = new_node; return; } if(mp.size() >= cp){ mp.erase(tail->key); auto new_tail = tail->prev; tail->prev->next = nullptr; tail = new_tail; } new_node->next = head; head->prev = new_node; head = new_node; mp[k] = new_node; } } int get(int k) override { if(mp.find(k) != mp.end()){ update_usage(k); return mp[k]->value; } else{ return -1; } } LRUCache(int capacity){ cp = capacity; } };
Here's my solution.
class LRUCache : public Cache{ private: void update_usage(int k){ // get the node pointed by the key // this function assumes k exists in mp auto node = mp[k]; // if this node is the head, or tail, there's no need for management if(node == head || node == tail) return; // otherwise, this node in the middle needs to be come the new head, and the rest pushed //node->prev should connect to node->next node->prev->next = node->next; // and also node->next->prev should point to node->prev node->next->prev = node->prev; // node->next should be head. node->prev = nullptr; // sever its prev connection node->next = head; // and it should point to the previous head head->prev = node; // also head's prev should point to node head = node; // and it should be come the new head } public: void set(int k, int v) override { // cout << "set fn called" << endl; // the removing and adding to key will happen by map for O(1) operations // also at the same time use doubly linked list to take care of "recency", and same O(1) // operations to add and remove in parallel with the map operations if(mp.find(k) != mp.end()){ // cache hit // if cache is hit, then no need to add/remove any to the map, cp stays the same // however recency deque should get updated // and also of course the node's value mp[k]->value = v; update_usage(k); } else{ // cache miss // create a node based on k and v Node* new_node = new Node(k, v); // if head and tail are empty, need to initialize them if(head == nullptr){ // cout << "initialization" << endl; head = new_node; tail = new_node; mp[k] = new_node; return; // there's no dequeu list maintenance needed } // if head was initialized, then need to check if capacity is reached if(mp.size() >= cp){ // then the least used one, the tail, should be discarded mp.erase(tail->key); // from map auto new_tail = tail->prev; tail->prev->next = nullptr; // from deque // also need to assign a new tail tail = new_tail; } // and should be added on the left side of the old head, and update the head new_node->next = head; head->prev = new_node; head = new_node; mp[k] = new_node; } } int get(int k) override { // cout << "hello in get" << endl; if(mp.find(k) != mp.end()){ // update the deque list accordingly update_usage(k); return mp[k]->value; } else{ return -1; } } LRUCache(int capacity){ cp = capacity; } };
Am getting wrong answer for 10/12 test cases. ive manually matched my output for over 150 inputs from one of the cases so far and i cant find any value wrong. can someone please tell me what am doing wrong?
class LRUCache:protected Cache { public: long int sizecap; LRUCache (int c){ sizecap=c; } void set(int k,int v) { if (mp.empty()) { Node* element = new Node(k,v); head=element; tail=element; mp[0]=element; // cout<<"1st value set"< bool exists=false; int ifexistkey; int size=mp.size(); for (long int i=0; ikey==k) { exists=true; ifexistkey=i; break; } } if (exists==true) {
if (ifexistkey==mp.size()-1) { tail=mp[ifexistkey]->prev; // cout<<"prev set as tail"<<endl; mp[ifexistkey]->next=head; // cout<<"head set as next"<<endl; head->prev=mp[ifexistkey]; // cout<<"head's prev set"<<endl; head=mp[ifexistkey]; } else if (ifexistkey==0) { mp[ifexistkey]->value=v; } else{ mp[ifexistkey]->prev->next=mp[ifexistkey]->next; mp[ifexistkey]->next->prev=mp[ifexistkey]->prev; mp[ifexistkey]->next=head; head->prev=mp[ifexistkey]; head=mp[ifexistkey]; } for (int i=1; i<=ifexistkey; i++) { mp[i]=mp[i]->prev; } mp[0]=head; // head->next=head+1; // mp[ifexistkey+1]->prev=mp[ifexistkey]; // mp[ifexistkey]->next=mp[ifexistkey+1]; } else if(exists==false){ Node* element = new Node(k,v); int size=mp.size(); if (size==sizecap) { // cout<<"size cap case"<<endl; tail=tail->prev; // cout<<"tail set"<<endl; mp.erase(sizecap-1); // cout<<"erased"<<endl; element->next=head; head->prev=element; head=element; mp[0]=element; int size=mp.size(); for (int i=1; i<size; i++) { mp[i]=mp[i-1]->next; } } else{ element->next=head; // cout<<"og head set as next"<<endl; head->prev=element; // cout<<"element set as prev of og head"<<endl; head=element; // cout<<"element is made new head"<<endl; mp[0]=element; // cout<<"element is set as 0 key on map"<<endl; int size=mp.size(); for (int i=1; i<=size; i++) { mp[i]=mp[i-1]->next; } // cout<<"value at"<<k<<"set"<<endl; } } } } int get(int keyval){ bool exists=false; int ifexistkey; int size=mp.size(); for (int i=0; i<size; i++) { if (mp[i]->key==keyval) { exists=true; ifexistkey=i; break; } } if (exists==true) { return mp[ifexistkey]->value; } else{ return -1; } }};
Mine has required destructors to free allocated memory, also it implements and underlying class
LRUCacheListto deal with everything related with list's stuff.Compile with -DDEBUG option, to see what is done in background (user SMALL input files to this case).
#include <iostream> #include <vector> #include <map> #include <string> #include <algorithm> #include <set> #include <cassert> using namespace std; struct Node{ Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; }; class Cache{ protected: map<int,Node*> mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer virtual void set(int, int) = 0; //set function virtual int get(int) = 0; //get function }; ostream &operator<<(ostream &o, const Node *n) { return o << '<' << n->key << ", " << n->value << '>'; //<< ", me: " << (void *)n; //<< ", prev: " << n->prev << ", next: " << n->next; } // This is the double-linked list internally used by the LRUCache class LRUCacheList { Node *head; Node *tail; int size; public: LRUCacheList() : head(NULL), tail(NULL), size(0) {} Node *getHead() const { return head; } Node *getTail() const { return tail; } int getSize() const { return size; } bool empty() const { return head != NULL; } ~LRUCacheList() { //cout << "called destructor ~LRUCacheList()\n"; Node *n = head, *np; while (n) { np = n->next; //cout << "freeing " << (void *)n << endl; delete n; n = np; } head = tail = NULL; size = 0; } /** Removes the last (tail) element of the cache-list */ void removeTail() { if (tail != NULL) { if (tail->prev != NULL) tail->prev->next = NULL; Node *new_tail = tail->prev; if (head == tail) { head = NULL; } delete tail; tail = new_tail; } if (size > 0) --size; } /** Inserts a new element at the head of the cache-list */ Node* insertFront(int key, int value) { /** Create a node (that will be the new head) with; * - prev: NULL * - next: former head */ Node *new_head = new Node(NULL, head, key, value); // attach it as the head the list if (head != NULL) { head->prev = new_head; head = new_head; } else { // empty list head = new_head; tail = new_head; } ++size; return head; } /** Moves a given node to the first position of the list. */ void promoteFront(Node *n) { if (head == n) return; if (n == tail) { tail = tail->prev; tail->next = NULL; } else { n->prev->next = n->next; n->next->prev = n->prev; } // attach it as the head the list if (head != NULL) { head->prev = n; } else { // empty list tail = n; } n->prev = NULL; n->next = head; head = n; } /** Prints out the content of the list */ friend ostream &operator<<(ostream &o, const LRUCacheList &l) { Node *n = l.getHead(); while (n) { if (n != l.getHead()) { o << ", "; } o << n; n = n->next; } o << ", size(" << l.size << ")"; return o; } }; class LRUCache: public Cache { protected: int size_; LRUCacheList l_; public: LRUCache(int capacity) : size_(0) { Cache::cp = capacity; } /** * set() - Set/insert the value of the key, if present, otherwise add the key * as the most recently used key. If the cache has reached its capacity, * it should replace the least recently used key with a new key. */ virtual void set(int key, int val) { // look at the key in the map pair<map<int,Node*>::iterator, bool> ret = mp.insert({key, NULL}); //auto [it, found] = mp.insert({key, NULL}); // c++17 map<int,Node*>::iterator it = ret.first; //cout << (ret.second ? "true: " : "false: ") << "it->first: " << it->first << endl; //<< ", " << (it->second ? it->second : "NULL") << endl; //exit(0); if (ret.second == true) { // inserts the new element if (l_.getSize() == cp) { mp.erase(l_.getTail()->key); l_.removeTail(); } it->second = l_.insertFront(key, val); } else { // element already existed: // (1) update value // (2) promote it at the front of the list it->second->value = val; l_.promoteFront(it->second); } // update members that refer to the underlying linked-list size_ = l_.getSize(); head = l_.getHead(); tail = l_.getTail(); #ifdef DEBUG cout << "set " << key << ' ' << val << endl; cout << "list is:\n " << l_ << endl; cout << "map is:\n"; for (auto &it: mp) { cout << " " << it.first << ", " << it.second << endl; } #endif } /** * get() - Get the value (will always be positive) of the key if the key exists * in the cache, otherwise return -1. */ virtual int get(int key) { map<int,Node*>::iterator it = mp.find(key); if (it != mp.end()) { // THIS SHOULDN'T BE THIS WAY // This method IS NOT intended to change the structure // BUT, as per the specifications, it must promote the element // as the first of the list, if found l_.promoteFront(it->second); it->second = l_.getHead(); #ifdef DEBUG cout << "get " << key << endl; cout << "list is:\n " << l_ << endl; cout << "map is:\n"; for (auto &it: mp) { cout << " " << it.first << ", " << it.second << endl; } #endif return it->second->value; } else { return -1; } } }; void testList() { LRUCacheList l; l.insertFront(1, 10); cout << "l:\n " << l << endl; l.insertFront(2, 11); cout << "l:\n " << l << endl; l.insertFront(3, 12); cout << "l:\n " << l << endl; cout << "now, remove tail\n"; l.removeTail(); cout << "l:\n " << l << endl; l.removeTail(); cout << "l:\n " << l << endl; l.removeTail(); cout << "l:\n " << l << endl; l.removeTail(); cout << "l:\n " << l << endl; l.insertFront(1, 10); cout << "l:\n " << l << endl; l.insertFront(2, 11); cout << "l:\n " << l << endl; l.insertFront(3, 12); cout << "l:\n " << l << endl; cout << "Promote first\n"; l.promoteFront(l.getHead()); cout << "l:\n " << l << endl; l.promoteFront(l.getHead()->next); cout << "l:\n " << l << endl; l.promoteFront(l.getHead()->next->next); cout << "l:\n " << l << endl; } int main() { int n, capacity,i; //testList(); //exit(0); cin >> n >> capacity; LRUCache l(capacity); for(i=0;i<n;i++) { string command; cin >> command; if(command == "get") { int key; cin >> key; cout << l.get(key) << endl; } else if(command == "set") { int key, value; cin >> key >> value; l.set(key,value); } } return 0; }
Load more conversations
Sort 305 Discussions, By:
Please Login in order to post a comment