C++实现LRU缓存时push_back无匹配成员函数报错排查

问题根因 #

C++完全支持创建存储迭代器的vector，该报错和vector存储能力无关，核心原因有两点：

• 代码缺失<vector>头文件引用，编译器无法识别vector类型的相关方法
• std::list的迭代器是类类型对象，不是原生指针，不支持和nullptr/NULL做隐式转换、赋值、比较。你代码中调用hash.push_back(nullptr)、给迭代器赋值nullptr、将迭代器和nullptr对比时，编译器找不到匹配的重载函数，就会抛出该错误。你尝试用vector<list<pair<int, int>>::iterator> hash(3001,NULL);初始化也会失败，因为NULL本质是整型值0，同样无法隐式转换为list迭代器。

修复逻辑 #

用list的尾后迭代器lru.end()代替nullptr作为空标记：lru.end()指向list末尾不存在的元素，天然可以用来标记“对应key不存在于缓存中”的状态，是合法的迭代器值。
具体修改点：

• 补全必要头文件：引入<vector>，手动引入<utility>保证pair类型可识别
• 初始化hash向量时，填充值从nullptr改为lru.end()
• 所有判断key是否存在的逻辑，从和nullptr比较改为和lru.end()比较
• 所有清空hash位的逻辑，从赋值nullptr改为赋值lru.end()

修复后可运行代码 #

#include <list>
#include <vector>
#include <utility>

class LRUCache {
    std::list<std::pair<int,int>> lru;
    int cap;
    std::vector<std::list<std::pair<int, int>>::iterator> hash;
public:
LRUCache(int capacity) {
    cap = capacity;
    for(int i = 0; i <= 3000; i++)
        hash.push_back(lru.end());
}

int get(int key) {
    if(hash[key] != lru.end())
    {
        int v = hash[key]->first;
        lru.erase(hash[key]);
        lru.push_front({v, key});
        hash[key] = lru.begin();
        return v;
    }
    return -1;
}

void put(int key, int value) {
    if(hash[key] != lru.end())
    {
        lru.erase(hash[key]);
        lru.push_front({value, key});
        hash[key] = lru.begin();
    }
    else if(lru.size() < cap)
    {
        lru.push_front({value, key});
        hash[key] = lru.begin();
    }
    else
    {
        lru.push_front({value, key});
        hash[key] = lru.begin();
        auto it = lru.end();
        it--;
        hash[it->second] = lru.end();
        lru.erase(it);
    }
}
};

内容的提问来源于stack exchange，提问作者shreyansh nammu