Что может вызвать ошибку времени выполнения в этой реализации LRU (хэш-карта и двусвязный список)?

Я получаю ошибку времени выполнения в LeetCode, но это отлично работает в моей системе Linux за 0,046 пользовательского времени для самого большого тестового примера. Результат точно соответствует ожидаемому результату LeetCode. В моем решении используется хэш-карта и двусвязный список. В хэш-карте хранится итератор для узла связанного списка (в дополнение к паре ключ->значение), чтобы список можно было обновить O (1) вместо O (n). Он работает для нескольких тестовых наборов, но я получаю ошибку времени выполнения в тестовом наборе с размером кеша 512 и инструкциями 2019.

class LRUCache {
public:
    LRUCache(int _capacity) { capacity = _capacity; }    
    int get(int key) {
        if(hmap.find(key) == hmap.end()) return -1;
        addq(key);
        return hmap[key].first;
    }    
    void put(int key, int value) {
        list<int>::iterator ptr = addq(key);
        hmap[key] = make_pair(value, ptr);
    }
private:
    list<int> q;
    unordered_map<int, pair<int,list<int>::iterator>> hmap;
    int capacity;
    list<int>::iterator addq(int key) {
        if(hmap.find(key) == hmap.end()) {
            if(q.size() == capacity) {
                int to_pop = q.back();
                hmap.erase(to_pop);
                q.pop_back();
            }                        
        }
        else q.erase(hmap[key].second);
        return q.insert(q.begin(), key);
    }
};

c++ runtime-error hashmap linked-list lru
person Derrick Sonnier    schedule 31.01.2019    source источник
comment
Что вы подразумеваете под ошибкой времени выполнения?   -  person YSC    schedule 31.01.2019
comment
Каково ваше сообщение об ошибке?   -  person Rafsan Mobasher    schedule 31.01.2019
comment
но я получаю ошибку времени выполнения в тестовом наборе с размером кеша 512 и инструкциями 2019. -- Итак, получите тестовый пример, прочитайте его, запустите свой код, отладьте.   -  person PaulMcKenzie    schedule 31.01.2019
comment
@YSC Все, что он говорит, это Статус: Ошибка выполнения без другой полезной информации.   -  person Derrick Sonnier    schedule 31.01.2019
comment
@PaulMcKenzie Я сделал именно это на локальном компьютере и получил ожидаемый результат Leetcode именно на моем локальном компьютере (они были достаточно хороши, чтобы предоставить мне это), но получил эту ошибку времени выполнения, когда попытался представить это как решение.   -  person Derrick Sonnier    schedule 31.01.2019

Ответы (1)


arrow_upward
0
arrow_downward

Возникла проблема с вашей функцией get (int key). Когда вы получаете доступ к кешу, вы должны сделать запись недействительной и обновить свои итераторы. Вы делаете это с помощью функции addq, но никогда не обновляете соответствующую запись в hmap. Поэтому возникает ошибка времени выполнения, потому что вы затем обращаетесь к итератору, который уже признан недействительным вашей функцией addq.

Глядя на следующий фрагмент:

if(hmap.find(key) == hmap.end()) return -1;
addq(key);
return hmap[key].first;

addq возвращает итератор, но вы никогда не обновляете итератор на своей карте, поэтому это должно быть:

hmap[key].second = addq(key);
person Samer Tufail    schedule 01.02.2019
comment
Отличное объяснение, Самер. Спасибо. Я предположил (ошибочно), что итераторы операции get обновляются в функции addq. - person Derrick Sonnier; 01.02.2019