A sample of a LRU Cache

lru_cache.cpp

#include <iostream>
#include <vector>
#include <map>

template <typename T>
struct CircularQueue {
    std::pair<T, T> data;
    size_t size;
    CircularQueue* prev, *next;
    CircularQueue(std::pair<T, T> data = std::make_pair(0, 0)) { this->data = data;  prev = next = nullptr; size = 0; }
    CircularQueue<T>* insert(CircularQueue* front, std::pair<T, T> data) {
        if (!front) {
            front = new CircularQueue(data);
            front->size++;
            return front;
        }
        if (!(front->prev)) {
            CircularQueue* node = new CircularQueue(data);
            node->next = node->prev = front;
            front->next = front->prev = node;
            node->size = front->size + 1;
            front = node;
            return front;
        }
        CircularQueue* rear = front->prev;
        CircularQueue* node = new CircularQueue(data);
        node->next = front;
        node->prev = rear;
        rear->next = node;
        front->prev = node;
        node->size = front->size + 1;
        front = node;
        return front;
    }
    CircularQueue<T>* remove(CircularQueue* front) {
        CircularQueue* rear = front->prev;
        if (!rear) {
            front->prev = nullptr;
            front->next = nullptr;
            delete front;
            return nullptr;
        }
        CircularQueue* tmp = rear->prev;
        if (tmp == front) {
            rear->prev = rear->next = nullptr;
            delete rear;
            front->prev = front->next = nullptr;
            front->size--;
            return front;
        }
        tmp->next = front;
        rear->prev = nullptr;
        front->prev = tmp;
        rear->next = nullptr;
        delete rear;
        front->size--;
        return front;
    }
    void print(CircularQueue* front) {
        if (!front)
            return;
        size_t cap;
        CircularQueue* head = front;
        for (cap = front->size; cap > 0; head = head->next) {
            std::cout << "Key: " << head->data.first << " -> ";
            cap--;
        }
        std::cout << "\n";
    }
    void free_queue(CircularQueue* front) {
        if (!front)
            return;
        front = this->remove(front);
        free_queue(front);
    }
};

template <typename T>
class LRUCache {
    // The LRUCache class: Implements a Least Recently Used policy
public:
    size_t capacity;
    size_t curr = 0;
    std::map<int, CircularQueue<T>*> hash_map;
    CircularQueue<T> queue;
    CircularQueue<T>* front;
    LRUCache(size_t capacity) {
        this->capacity = capacity;
        std::pair<T, T> pr = std::make_pair(0, 0);
        queue = CircularQueue<T>(pr);
        front = nullptr;
    }
    int get(int key) {
        if (hash_map.count(hash(key)) > 0) {
            if (curr == 1)
                return hash_map[key]->data.second;
            CircularQueue<T>* node = hash_map[hash(key)];
            CircularQueue<T>* pnode = node->prev;
            CircularQueue<T>* nnode = node->next;
            if (pnode && pnode == nnode) {
                front = node;
                front->size = curr;
                return hash_map[key]->data.second;
            }

            if (pnode) {
                pnode->next = nnode;
            }
            if (nnode) {
                nnode->prev = pnode;
            }
            node->next = front;
            node->prev = front->prev;
            if (front->prev)
                front->prev->next = node;
            CircularQueue<T>* tmp = front;
            tmp->prev = node;
            front = node;
            front->size = curr;
            //front = queue.remove(front);
            //front = queue.insert(front, key);
            return hash_map[key]->data.second;
        }
        return -1;
    }
    void put(int key, int value) {
        if (hash_map.count(hash(key)) > 0) {
            if (curr == 1) {
                front->data.second = value;
                return;
            }
            CircularQueue<T>* node = hash_map[hash(key)];
            CircularQueue<T>* pnode = node->prev;
            CircularQueue<T>* nnode = node->next;
            if (pnode && (pnode == nnode)) {
                front = node;
                front->size = curr;
                front->data.second = value;
                return;
            }

            if (pnode) {
                pnode->next = nnode;
            }
            if (nnode) {
                nnode->prev = pnode;
            }
            node->next = front;
            node->prev = front->prev;
            if (front->prev)
                front->prev->next = node;
            CircularQueue<T>* tmp = front;
            tmp->prev = node;
            front = node;
            front->size = curr;
            front->data.second = value;
            return;
        }
        if (curr >= capacity) {
            if (front->prev)
                hash_map.erase(hash(front->prev->data.first));
            else
                hash_map.erase(hash(front->data.first));
            front = queue.remove(front);
            curr--;
        }
        std::pair<T, T> pr = std::make_pair(key, value);
        front = queue.insert(front, pr);
        curr++;
        hash_map[hash(front->data.first)] = front;
        // std::cout << "Inserted " << front->data << " to queue\n";
    }
    int hash(int key) {
        return key;
    }
    void print() {
        queue.print(front);
    }
    ~LRUCache() {
        hash_map.clear();
        queue.free_queue(front);
    }
};

int main() {
    LRUCache<int> cache(2); // We can choose between a vector and a map for the HashMap Table
    cache.put(1, 1);
    cache.put(2, 2);
    cache.print();
    std::cout <<  cache.get(1) << std::endl;       // returns 1
    cache.print();
    cache.put(3, 3);    // evicts key 2
    std::cout << cache.get(2) << std::endl;       // returns -1
    cache.put(4, 4);    // evicts key 1
    std::cout << cache.get(1) << std::endl;       // returns -1 (not found)
    std::cout << cache.get(3) << std::endl;       // returns 1
    std::cout << cache.get(4) << std::endl;       // returns 1
    return 0;
}