I am implementing an LRU cache for a problem where I need to store key value pairs.

I am storing the values in a linked list which is a queue in the order of most recently accessed, and I keep the key, and a pointer to the value node in an unordered_map in <key,*ptr> type. I am doing this to ensure constant time complexity for all the methods in the cache.

So in the put method of my class, I have a check to see if the key is already present in my map

if (mymap.find(key) != mymap.end())

The issue is:-

• The value of this expression is always returning true

• The key value I am doing the check for is being added to the map

eg- the map has <1,1> in it

• if I try to insert <2,3>, it goes to the “found in map case” even thought key 2 is not in map.
• and instead of <1,1> the whole map has only <2, > in it.

here’s the relevant part of the method

void put(int key, int value) {
        Node* temp;
        cout << "nnTrynna put " << key << " & " << value;
        cout << "nbefore:";
        printMap();

        if (start == NULL) {
            // if else conditions for other cases
            .
            .
            .
        } else if (mymap.find(key) != mymap.end()) { //BUGGY PART

            cout << "-> case found";
            cout << "nafter:";
            printMap();

            mymap[key]->data = value;
            mymap[key]->prev->next = mymap[key]->next;
            mymap[key]->next->prev = mymap[key]->prev;
            end->next = mymap[key];
            mymap[key]->prev = end;
            end = mymap[key];
        } else {
            cout << "-> case not found ";
            if (cap == 0) {
                mymap.erase(start->key);
                temp = start;
                start = start->next;
                if (start != NULL)
                    start->prev = NULL;
                delete temp;
                cap++;
            }
            if (start == NULL) {
                start = end = new Node(key, value);
                mymap[key] = end;
                cap--;
            } else {
                end->next = new Node(key, value, end);
                end = end->next;
                mymap[key] = end;
                cap--;
            }
        }
        cout << "nafter:";
        printMap();
        printData();
    }

here’s the whole class, including the tips on how the code is run in the main method

class Node {
public:
    int key;
    int data;
    Node* next;
    Node* prev;
    Node(int key, int data) : key(key), data(data), next(NULL), prev(NULL) {}
    Node(int key, int data, Node* prev)
        : key(key), data(data), next(NULL), prev(prev) {}
};

class LRUCache {
public:
    unordered_map<int, Node*> mymap;
    Node* start;
    Node* end;
    int cap;
    int capacity;
    LRUCache(int capacity)
        : mymap(), start(NULL), end(NULL), cap(capacity), capacity(capacity) {}

    void printMap() {
        for (auto node : mymap)
            cout << "nkey: " << node.first << ", value: " << node.second->data;
    }
    void printData() {
        if (start != NULL && end != NULL)
            cout << "nstart: " << start->key << ", end: " << end->key;
        if (end != start)
            cout << ", prev: " << end->prev->key;
        cout << "n cap: " << cap;
    }

    int get(int key) {
        cout << "nnTrynna get " << key;
        Node* temp;

        if (mymap.find(key) == mymap.end())

            return -1;
        if (mymap[key] != end) {
            if (mymap[key] == start) {
                start = start->next;
            } else {
                mymap[key]->prev->next = mymap[key]->next;
                mymap[key]->next->prev = mymap[key]->prev;
            }

            end->next = mymap[key];
            temp = end;
            end = end->next;
            end->prev = temp;
            mymap[key]->next = NULL;
        }

        for (auto node : mymap) {
            cout << "nkey: " << node.first << ", value: " << node.second->data;
        }
        cout << "nstart: " << start->key;
        if (end != start)
            cout << ", end: " << end->key << ", prev: " << end->prev->key;

        return mymap[key]->data;
    }

    void put(int key, int value) {
        Node* temp;
        cout << "nnTrynna put " << key << " & " << value;
        cout << "nbefore:";
        printMap();
        if (start == NULL) {
            cout << "-> case NULL";
            start = end = new Node(key, value);
            mymap[key] = end;
            cap--;
        } else if (mymap[key] == end) {
            cout << "-> case end";
            end->data = value;
        } else if (mymap[key] == start) {
            cout << "-> case start";
            start = mymap[key]->next;
            start->prev = NULL;
            mymap[key]->prev = end;
            mymap[key]->next = NULL;
            end = mymap[key];
        } else if (mymap.find(key) != mymap.end()) {
            cout << "-> case found";
            cout << "nafter:";
            printMap();
            mymap[key]->data = value;
            mymap[key]->prev->next = mymap[key]->next;
            mymap[key]->next->prev = mymap[key]->prev;
            end->next = mymap[key];
            mymap[key]->prev = end;
            end = mymap[key];
        } else {
            cout << "-> case not found ";
            if (cap == 0) {
                mymap.erase(start->key);
                temp = start;
                start = start->next;
                if (start != NULL)
                    start->prev = NULL;
                delete temp;
                cap++;
            }
            if (start == NULL) {
                start = end = new Node(key, value);
                mymap[key] = end;
                cap--;
            } else {
                end->next = new Node(key, value, end);
                end = end->next;
                mymap[key] = end;
                cap--;
            }
        }
        cout << "nafter:";
        printMap();
        printData();
    }
};
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */