c++ - LRU 缓存 C++ 实现问题

Question

我在做一个在线判断的练习:

为最近最少使用 (LRU) 缓存设计和实现数据结构。它应该支持以下操作:获取和设置。

get(key) - 如果缓存中存在该键，则获取该键的值(始终为正值)，否则返回 -1。

set(key, value) - 如果键不存在，则设置或插入值。当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目无效。

我基本上使用 std::list 和 std::unordered_map 并且在小输入情况下效果很好。但是 OJ 在输入上给出了超出时间限制:缓存大小为 2048 和 20000+ get & set 操作。

超时版本:

class LRUCache {
public:
    LRUCache(int capacity):cacheSize(capacity) {

    }
    int get(int key) {
        auto it = mapping.find(key);
        if(it == mapping.end())
            return -1;
        itemList.splice(itemList.begin(),itemList,it->second);
        //mapping[key] == it->second still holds
        return it->second->second;
    }
    void set(int key, int value) {
        auto it = mapping.find(key);
        if(it != mapping.end()) {
            itemList.splice(itemList.begin(),itemList,it->second);
            it->second->second = value;
        } else {
            itemList.push_front(make_pair(key,value));
            mapping.insert(make_pair(key,itemList.begin()));
        }
        if(itemList.size() > cacheSize) {
            mapping.erase(itemList.back().first);
            itemList.pop_back();
        }
    }
private:
    int cacheSize;
    list<pair<int,int> > itemList;
    unordered_map<int,list<pair<int,int> >::iterator> mapping;
};

然后我想为什么不在插入一个元素之前删除元素，所以我修改了set函数并OJ接受!

接受版本:

    void set(int key, int value) {
        auto it = mapping.find(key);
        if(it != mapping.end()) {
            itemList.splice(itemList.begin(),itemList,it->second);
            it->second->second = value;
        } else {
            if(itemList.size() == cacheSize) {
                mapping.erase(itemList.back().first);
                itemList.pop_back();
            }
            itemList.push_front(make_pair(key,value));
            mapping.insert(make_pair(key,itemList.begin()));
        }
    }

我想知道是什么让情况如此不同？

Answer 1

原因是您使用的 OJ 使用 C++ 编译器，该编译器的 std::list::size 具有线性复杂度。在 C++11 中，他们要求它是常量，但在 C++98 中，它可能是线性的，许多实现实际上是线性的。

请参阅C++98 选项卡上的complexity:http://www.cplusplus.com/reference/list/list/size/

我找到了您正在使用的 OJ，并设法通过您的代码获得了 TLE，但通过一个小的修改设法让它被接受，它只是跟踪列表的大小而不是调用 size()

class LRUCache {
public:
    LRUCache(int capacity):cacheSize(capacity) {
        listSize = 0;
    }
    int get(int key) {
        auto it = mapping.find(key);
        if(it == mapping.end())
            return -1;
        itemList.splice(itemList.begin(),itemList,it->second);
        //mapping[key] == it->second still holds
        return it->second->second;
    }
    void set(int key, int value) {
        auto it = mapping.find(key);
        if(it != mapping.end()) {
            itemList.splice(itemList.begin(),itemList,it->second);
            it->second->second = value;
        } else {
            itemList.push_front(make_pair(key,value));
            ++ listSize;
            mapping.insert(make_pair(key,itemList.begin()));
        }
        if(listSize > cacheSize) {
            mapping.erase(itemList.back().first);
            -- listSize;
            itemList.pop_back();
        }
    }
private:
    int cacheSize;
    int listSize;
    list<pair<int,int> > itemList;
    unordered_map<int,list<pair<int,int> >::iterator> mapping;
};