0

leetcode の練習をしていると、次のような問題に遭遇しました。

stl::listLRU アルゴリズムのキャッシュとしてコンテナーを使用しました。しかし、アイテムを消去してアイテムを挿入する順序は結果を変えました。

私はそれが実際には二重リストであることを知ってい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

あなたが何を求めているのかははっきりしていません。これらの 2 つの行を並べ替えることができない理由について質問がある場合は、次のようにします。

    //**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 に答える