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
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.
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)));
}
User contributions licensed under CC BY-SA 3.0