3
\$\begingroup\$

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

 };
\$\endgroup\$
  • \$\begingroup\$ Have you considered iterator based interface? I assume this is some sort of container, so it should be viable idea. \$\endgroup\$ – Incomputable Sep 4 '17 at 16:52
7
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.