C++ LRU缓存迭代器循环依赖问题求解

问题背景 #

我尝试快速实现LRU缓存，原本用std::unordered_map存储键值对，std::list存储指向map元素的迭代器来维护访问顺序。但为了在map中同时存储对应list节点的迭代器（用于快速移动链表节点），修改map的定义后出现了循环依赖：

• 修改后的values_map需要order_list的迭代器类型作为值的一部分
• 而order_list又需要values_map的迭代器类型作为存储元素

最初的类型定义：

template<class K, class V>
class LruCache
{
public:
    typedef std::unordered_map<K, V> values_map;
    typedef std::list<typename values_map::iterator> order_list; // list存储map迭代器
};

当要在map中加入list迭代器时，新的定义导致循环：

typedef std::unordered_map<K, std::pair<V, typename order_list::iterator>> values_map;

当前错误实现代码 #

为了编译强行使用reinterpret_cast，但GCC会报错，错误位置已标记：

#include <list>
#include <unordered_map>
#include <string>

template<class K, class V>
class LruCache
{
public:
    LruCache()
    {
        maxSize = 3;
    }

    size_t size() const
    {
        return values.size();
    }

    void set(const K& key, const V& value)
    {
        auto pos = values.find(key);
        if (pos == values.end())
        {
            order.push_front(typename order_list::value_type()); // 先插入空元素，后续更新
            auto pos2 = values.emplace(key, std::make_pair(value, order.begin()));
            order.front() = reinterpret_cast<typename order_list::value_type&>(pos2.first); // ERROR：类型不匹配，强制转换无效
            if (size() > maxSize)
            {
                values.erase(reinterpret_cast<typename values_map::iterator&>(order.back())); // ERROR：类型不匹配
                order.pop_back();
            }
        }
        else
        {
            pos->second.first = value;
            typename order_list::iterator it = pos->second.second;
            if (it != order.begin()) // 将访问过的节点移到链表头部
                order.splice(order.begin(), order, it, std::next(it));
        }
    }

private:
    typedef std::unordered_map<K, V> values_map_;
    typedef std::list<typename values_map_::iterator> order_list; // 此处迭代器对应旧的map类型，与最终values_map不兼容
    typedef std::unordered_map<K, std::pair<V, typename order_list::iterator>> values_map;

    values_map values;
    order_list order;
    size_t maxSize;
};


int main()
{
    LruCache<std::string, std::string> test;

    test.set("1", "1");
    test.set("2", "2");
    test.set("3", "3");
    test.set("4", "4");
}

需求 #

希望在不调整核心数据布局（即保持list存储map迭代器、map存储list迭代器的双向引用结构）的前提下，解决这个循环依赖问题。

内容的提问来源于stack exchange，提问作者Pavel P