What's wrong with my LRU? Did I use std::deque mistakenly?

user_6193296 0
Viewed 92

I'm quite frustrated about this, now I'm still have absolutely no clues why am I getting wrong. So I'm doing LRU implementation as following:

#include <iostream>
#include <unordered_map>
#include <deque>
#include <list>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {
        cache.clear();
        pos_map.clear();
    }
    void check_recent() {
        cout << "recent: ";
        for (auto it : cache)
            cout << it << " ";
        cout << endl;
    }
    int get(int key) {
        cout << "get: " << key << " ; ";
        auto it = pos_map.find(key);
        if (it != pos_map.end()) {
            cache.erase(it->second.second);
            cache.push_front(key);
            pos_map[key].second = cache.begin();
            check_recent();
            return pos_map[key].first;
        } 
        check_recent();
        return -1;
    }
    
    void put(int key, int value) {
        cout << "put: " << key << ", " << value << " ; ";
        auto it = pos_map.find(key);
        if (it != pos_map.end()) {
            pos_map[key].first = value;
            cache.erase(it->second.second);
            cache.push_front(key);
            pos_map[key].second = cache.begin();
        } else {
            cache.push_front(key);
            if (cache.size() > cap) {
                int remove = cache.back();
                cache.pop_back();
                pos_map.erase(remove);
            }
            pos_map[key] = make_pair(value, cache.begin());
        }
        
        check_recent();
        return ;
    }
private:
    int cap;
    deque<int> cache; // deque of keys
    unordered_map<int, pair<int, deque<int>::iterator>> pos_map;
    // <key, <value, iter>>
};

int main()
{
    cout<<"Hello World\n";
    LRUCache* obj = new LRUCache(10);
    obj->put(10, 13);
    obj->put(3, 17);
    obj->put(6, 11);
    obj->put(10, 5);
    obj->put(9, 10);
    obj->get(13);
    obj->put(2, 19);
    obj->get(2);
    obj->get(3);
    obj->put(5, 25);
    obj->put(9, 22);
    obj->put(5, 5);
    obj->put(1, 13);
    obj->put(9, 12);
    return 0;
}

Then I get the following output:

Hello World
put: 10, 13 ; recent: 10 
put: 3, 17 ; recent: 3 10 
put: 6, 11 ; recent: 6 3 10 
put: 10, 5 ; recent: 10 6 3 
put: 9, 10 ; recent: 9 10 6 3 
get: 13 ; recent: 9 10 6 3 
put: 2, 19 ; recent: 2 9 10 6 3 
get: 2 ; recent: 2 9 10 6 3 
get: 3 ; recent: 3 2 9 10 6 
put: 5, 25 ; recent: 5 3 2 9 10 6 
put: 9, 22 ; recent: 9 5 3 2 10 6 
put: 5, 5 ; recent: 5 9 3 2 10 6 
put: 1, 13 ; recent: 1 5 9 3 2 10 6 
put: 9, 12 ; recent: 9 1 "9" 3 2 10 6

This fault "9" costs me an hour to figure out why yet in vain. But the thing is, if I change all of the std::deque in my codes to std::list, the outcome is same as my expectation:

put: 9, 12 ; recent: 9 1 "5" 3 2 10 6

So what the heck is going on with std::deque::erase? Did I do something wrong? Can anybody guide my or gimme some clues plz? Thanks a lot

deque list c++
1 Answers

So what the heck is going on with std::deque::erase? Did I do something wrong?

You have two data structures, one of which maps to iterators of the other:

    deque<int> cache; // deque of keys
    unordered_map<int, pair<int, deque<int>::iterator>> pos_map;

If the iterators are to a dequeue, then the invalidation rules of erase state

All iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

However, for list we have

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

user_35107360
Related