LRU 缓存 C++ 实现问题

Question

我在做一个在线评委的练习：

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

get(key) - 如果缓存中存在键，则获取键的值（始终为正），否则 return -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 使用了具有 std::list::size 线性复杂度的 C++ 编译器。在 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;
};

LRU 缓存 C++ 实现问题

LRU Cache C++ implementation issue

c++

algorithm

caching

c++11