LRU cache implementation in C++ using unordered_map and doubly linked list

Question

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;
 }
 };

• Incomputable: Have you considered iterator based interface? I assume this is some sort of container, so it should be viable idea.

Answer 1

Code simplification

You don't need to use a custom linked list here. std::list will do fine, too.

You can keep the pairs (key, value) in an std::list and store a mapping from keys to iterators in this list in an std::unordered_map.

Passing by const reference

Passing keys and values by value creates an extra copy, which may be expensive. You can pass them by a const reference to avoid it.

Comments

Redundant comments clutter the code and hurt its readability, for instance:

// move the page to front
m_pageList->Move_Page_To_Front(m_pageMap[key]);

Delete this kind of comments.

API design

if (m_pageMap.find(key) == m_pageMap.end()) {
 return -1;
}

Returning -1 is a terrible idea. Firstly, -1 can be a valid value. Secondly, it won't compile for an arbitrary type of values, so it makes the use of your cache extremely limited.

Here're several ways to fix it:

1. Change the return type to std::optional<Value>. It works with C++17 only, but you can use boost::optional<Value> with earlier version of the standard.

2. If neither C++ 17 nor boost is available, you can return something that can either contain a value or be empty (like a smart pointer to a Value).

3. You can throw an exception if the key is missing.

4. You can insert a default value for the key and return it.

I prefer the first option as the optional type accurately reflects what may happen: there's either a value or nothing.