Когда я занимаюсь на 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));
}
}
};
Не совсем понятно, о чем вы спрашиваете. Если ваш вопрос, почему эти две строки не могут быть переупорядочены:
//**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
будет указывать на недавно вставленный узел списка, а не на ранее существовавший.
Других решений пока нет …