0

我在练习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));
    }

}
};
4

1 回答 1

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则将指向新插入的列表节点，而不是先前存在的节点。

于 2014-03-31T04:46:47.900 回答