I have implemented an LRU cache in C++ using a hash table and a doubly linked list. Any kind of feedback is appreciated.
#pragma once
#include<memory>
template<typename Key , typename Value>
class Node {
public:
Key key;
Value val;
std::shared_ptr<Node> next;
std::shared_ptr<Node> prev;
Node(Key k,Value v) :
key(k),
val(v),
next(nullptr),
prev(nullptr)
{}
};
template<typename Key, typename Value>
class List {
private:
std::shared_ptr<Node<Key, Value>> front;
std::shared_ptr<Node<Key, Value>> rear;
bool isEmpty() {
return rear == nullptr;
}
public:
List() : front(nullptr), rear(nullptr) {}
std::shared_ptr<Node<Key, Value>> Insert_Page_At_Front(Key k , Value v) {
std::shared_ptr<Node<Key, Value>> page = std::make_shared<Node<Key,
Value>>(k, v);
if (front == nullptr && rear == nullptr) {
front = page;
rear = page;
}
else {
page->next = front;
front->prev = page;
front = page;
}
return page;
}
void Move_Page_To_Front(std::shared_ptr<Node<Key, Value>> page) {
if (page == front) {
return;
}
if (page == rear) {
rear = rear->prev;
rear->next.reset();
}
else {
page->prev->next = page->next;
page->next->prev = page->prev;
}
page->next = front;
page->prev.reset();
front->prev = page;
front = page;
}
void remove_Page_From_Rear() {
if (isEmpty()) {
return;
}
if (front == rear) {
rear.reset();
front.reset();
rear.reset();
}
else
{
std::shared_ptr<Node<Key, Value>> temp = rear;
rear = rear->prev;
rear->next.reset();
temp.reset();
}
}
std::shared_ptr<Node<Key, Value>> Get_Rear_Page() {
return rear;
}
};
#pragma once
#include"List.h"
#include<unordered_map>
template<typename Key, typename Value>
class LRUCache {
private:
unsigned int m_capacity;
unsigned int m_currentSize;
std::unordered_map<Key, std::shared_ptr<Node<Key, Value>> > m_pageMap;
std::shared_ptr<List<Key,Value>> m_pageList;
public:
LRUCache(int Capacity) {
m_capacity = Capacity;
m_currentSize = 0;
m_pageList = std::make_shared<List<Key,Value>>();
}
Value get(Key key) {
if (m_pageMap.find(key) == m_pageMap.end()) {
return -1;
}
Value value = m_pageMap[key]->val;
// move the page to front
m_pageList->Move_Page_To_Front(m_pageMap[key]);
return value;
}
void put(Key key,Value value) {
if (m_pageMap.find(key) != m_pageMap.end()) {
// if key already present, update value and move page to head
m_pageMap[key]->val = value;
m_pageList->Move_Page_To_Front(m_pageMap[key]);
return;
}
if (m_currentSize == m_capacity) {
//remove rear page
Key k = m_pageList->Get_Rear_Page()->key;
m_pageMap.erase(k);
m_pageList->remove_Page_From_Rear();
m_currentSize--;
}
//add new page to front
std::shared_ptr<Node<Key, Value>> page = m_pageList
->Insert_Page_At_Front(key,value);
m_currentSize++;
m_pageMap[key] = page;
}
};