Блог пользователя YangZhao512

Автор YangZhao512, история, 8 лет назад, По-английски

Hope this post is not irrelevant to codeforces. I've spent lots of hours on this problem but just can't figure out what the problem is with my code. The OJ gives Runtime Error. Can anyone help me? Thanks a lot!

class LRUCache{
private:
    int cap;
    deque<int> keyList;
    map<int, deque<int>::iterator> pos;
    map<int, int> key2val;
    static const int FAIL = -1;

    void move2front(int key){
        keyList.erase(pos[key]);
        keyList.push_front(key);
        pos[key] = keyList.begin();
    }

    void evict(){
        int key = keyList.back();
        keyList.pop_back();
        pos.erase(key);
        key2val.erase(key);
    }

    void insert(int key, int val){
        keyList.push_front(key);
        key2val[key] = val;
        pos[key] = keyList.begin();
    }
public:
    LRUCache(int capacity) {
        cap = capacity;
        keyList.clear();
        pos.clear();
        key2val.clear();
    }

    int get(int key) {
        if(key2val.find(key) != key2val.end()){
            move2front(key);
            return key2val[key];
        }
        return FAIL;
    }

    void set(int key, int value) {
        if(pos.find(key) != pos.end()){
            move2front(key);
            key2val[key] = value;
        } else {
            if(keyList.size() == cap)  evict();
            insert(key, value);
        }
    }
};
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

didn't really checked your solution, but I guess that's because in this line

keyList.erase(pos[key]);

iterator pos[key] might be invalid. Google iterator invalidation rules for std::deque and replace it with std::list