c++ returning the value of an object inside a map

0

my problem is that i've a very basic Node class:

struct Node {
    Node* next;
    Node* prev;
    int value;
    int key;
    Node(Node* p, Node* n, int k, int val) :prev(p), next(n), key(k), 
value(val) {};
    Node(int k, int val) :prev(NULL), next(NULL), key(k), value(val) {};
};

Then a Cache class that stores a map of Node objects

class Cache {
protected:
    map<int, Node*> mp; //map the key to the node in the linked list
    int cp;  //capacity
    Node* tail; // double linked list tail pointer
    Node* head; // double linked list head pointer
    virtual void set(int, int) = 0; //set function
    virtual int get(int) = 0; //get function

};

Finally I've a LRUCache class that's derived from Cache class.

class LRUCache : public Cache {
public:
    LRUCache(int capacity) { cp = capacity; }
    virtual int get(int k) {
        std::map<int, Node*>::iterator it;
        it = mp.find(k);

        if (it != mp.end()) {
            return it->second->value;
        }
        else {
            return -1;
        }
    }

    virtual void set(int k, int v) {
        if (mp[k]) {
            mp[k] = new Node(k, v);
        }
        else {
            std::map<int, Node*>::iterator it = mp.begin();
            mp.insert(it, std::pair<int, Node*>(k, new Node(k, v)));
        }
    }
};

The error I'm experiencing is on the getter of this LRUCache class.

Returning this: "return it->second->value" gives me this error:

LRUCache.exe: 0xC0000005: Memory Access Violation while reading the path 0x00000008.

Why should it return me an error if the member value "value" is public on the Node struct?

Thanks in advance

c++
asked on Stack Overflow Jul 18, 2017 by freecloud • edited Jul 18, 2017 by freecloud

2 Answers

1
    if (mp[k]) {
        mp[k] = new Node(k, v);
    }
    else {
        std::map<int, Node*>::iterator it = mp.begin();
        mp.insert(it, std::pair<int, Node*>(k, new Node(k, v)));
    }

There are two possibilities there. If the map entry at k already exists and refers to a non-null Node, that Node is leaked and replaced with another Node (which makes little sense, but at least it doesn't immediately lead to crashing).

If the map entry doesn't exist, then mp[k] implicitly creates one, with nullptr as the value (it's also possible that it already exists and holds a null pointer; the end result is the same). You then proceed to call mp.insert() with the same key k - that does nothing, because the entry already exists. A Node is leaked here once again - but the main problem is that null pointer in the map.

When you next call get() with the same key, it retrieves the null pointer and promptly attempts to dereference it. That's where your program is crashing.

answered on Stack Overflow Jul 18, 2017 by Igor Tandetnik
0

Thank you Igor, as you said the problem was in the setter.

this refactor seems to work:

    if (mp.find(k) != mp.end()) {
        auto it = mp[k];
        it->value = v;
    }
    else {
        auto it = mp.begin(); 
        mp.insert(it, std::pair<int, Node*>(k, new Node(k, v)));
    }
answered on Stack Overflow Jul 18, 2017 by freecloud

User contributions licensed under CC BY-SA 3.0