последовательность вставки и удаления с использованием stl :: list

Когда я занимаюсь на leetcode, я столкнулся с такой проблемой:

Я использовал stl::list контейнер как кеш для алгоритма LRU. Но последовательность стирания элемента и вставки элемента изменила результат.

Я знаю, что это на самом деле двойной список stl::list, И последовательность вставки и удаления не должна иметь значения, когда я использую итератор.

Код здесь

class LRUCache{
public:

map<int, list<pair<int,int>>::iterator> mKey;
list<pair<int,int>> lCache;
int cap;LRUCache(int capacity) {
cap = capacity;
}

int get(int key) {
auto iter = mKey.find(key);
if(iter != mKey.end()) {
int value = (iter->second)->second;//**the sequence of next two lines can not be changed!***
lCache.erase(iter->second);
mKey[key] = lCache.insert(lCache.begin(), make_pair(key,value));

return value;
}
return -1;
}

void set(int key, int value) {
auto iter = mKey.find(key);
if(iter == mKey.end()) {
if(lCache.size() < cap) {
mKey[key] = lCache.insert(lCache.begin(), make_pair(key,value));
}
else{
mKey[key] = lCache.insert(lCache.begin(), make_pair(key,value));
mKey.erase(lCache.back().first);
lCache.pop_back();
}
}
else {
lCache.erase(iter->second);
mKey[key] = lCache.insert(lCache.begin(), make_pair(key,value));
}

}
};

0

Решение

Не совсем понятно, о чем вы спрашиваете. Если ваш вопрос, почему эти две строки не могут быть переупорядочены:

    //**the sequence of next two lines can not be changed!***
lCache.erase(iter->second);
mKey[key] = lCache.insert(lCache.begin(), make_pair(key,value));

тогда это просто. iter указывает на тот же узел, что и mKey[key]Таким образом, назначение фактически меняет значение iter->second, Если назначение произойдет первым, то iter->second будет указывать на недавно вставленный узел списка, а не на ранее существовавший.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]