LRU cache implementation in C++ using unordered_map and doubly linked list 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&lt;memory&gt;

template&lt;typename Key , typename Value&gt;
class Node {
  public:
    Key key;
    Value val;

    std::shared_ptr&lt;Node&gt; next;
    std::shared_ptr&lt;Node&gt; prev;

Node(Key k,Value v) : 
     key(k),
     val(v),
     next(nullptr),
     prev(nullptr)
  {}
};


template&lt;typename Key, typename Value&gt;
class List {
  private:  
    std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; front;
    std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; rear;

bool isEmpty() {
    return rear == nullptr;
 }

public:
List() : front(nullptr), rear(nullptr) {}

std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; Insert_Page_At_Front(Key k , Value v) {

    std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; page = std::make_shared&lt;Node&lt;Key, 
    Value&gt;&gt;(k, v);

    if (front == nullptr &amp;&amp; rear == nullptr) {
        front = page;
        rear = page;
    }
    else {
        page-&gt;next = front;
        front-&gt;prev = page;
        front = page;
    }
    return page;
  }

  void Move_Page_To_Front(std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; page) {
    if (page == front) {
        return;
    }
    if (page == rear) {
        rear = rear-&gt;prev;
        rear-&gt;next.reset();
    }
    else {
        page-&gt;prev-&gt;next = page-&gt;next;
        page-&gt;next-&gt;prev = page-&gt;prev;
    }

    page-&gt;next = front;
    page-&gt;prev.reset();
    front-&gt;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&lt;Node&lt;Key, Value&gt;&gt; temp = rear;
        rear = rear-&gt;prev;
        rear-&gt;next.reset();
        temp.reset();
    }
  }

  std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; Get_Rear_Page() {
    return rear;
  }

};


#pragma once
#include"List.h"
#include&lt;unordered_map&gt;

template&lt;typename Key, typename Value&gt;
class LRUCache {
private:
    unsigned int m_capacity;
    unsigned int m_currentSize;
    std::unordered_map&lt;Key, std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; &gt; m_pageMap;
    std::shared_ptr&lt;List&lt;Key,Value&gt;&gt; m_pageList;
public:
LRUCache(int Capacity) {
    m_capacity = Capacity;
    m_currentSize = 0;
    m_pageList = std::make_shared&lt;List&lt;Key,Value&gt;&gt;();
}

Value get(Key key) {
    if (m_pageMap.find(key) == m_pageMap.end()) {
        return -1;
    }
    Value value = m_pageMap[key]-&gt;val;

    // move the page to front
    m_pageList-&gt;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]-&gt;val = value;
        m_pageList-&gt;Move_Page_To_Front(m_pageMap[key]);
        return;
    }

    if (m_currentSize == m_capacity) {
        //remove rear page
        Key k = m_pageList-&gt;Get_Rear_Page()-&gt;key;
        m_pageMap.erase(k);
        m_pageList-&gt;remove_Page_From_Rear();
        m_currentSize--;
    }

    //add new page to front
    std::shared_ptr&lt;Node&lt;Key, Value&gt;&gt; page = m_pageList
    -&gt;Insert_Page_At_Front(key,value);
    m_currentSize++;
    m_pageMap[key] = page;
  }

 };
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-&gt;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:


Change the return type to std::optional&lt;Value&gt;. It works with C++17 only, but you can use boost::optional&lt;Value&gt; with earlier version of the standard.
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).
You can throw an exception if the key is missing.
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.