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

 };

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.