Circular dependency where two containers store iterators to each other's elememts

I wrote quick impl of LRU cache, where all the data (eg key -> value pairs) is stored in unordered map, and the order list simply stored pointers to these items.

if it was regular C data structs, things would be easy. However, with c++ I have an issue here:

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 of iterators into values_map
};

However, I also need to store reference to the node in the list inside the map. Not a problem, iterator into the order list can be added to the map:

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

That's where it gets tricky: values_map is now changed, which makes it incompatible with order_list that cannot store iterators into values_map anymore. Effectively, there is now circular dependency between these values_map and order_list.

What can be done to resolve the dependency without restructuring the data layout, eg. list should only contain pointers/iterators into the map.

Here's sample code: https://godbolt.org/z/YabKPxP3Y

#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()); // will update with correct value once value is created in `values`
            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()) // move list node to the front
                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; // values are values_map::iterator
    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");
}

I marked places of issue with ERROR comment and to force it I use reinterpret_cast to make it compile (note, gcc complains on there).

When I asked deepseek to resolve the dependency making sure the layout is preserved it went into this mode (I had to abort it, otherwise, it would endlessly keep typing the recursing types):

Typedef for a list can be declared with non fully defined type:

https://godbolt.org/z/Y7EYE63M8

This make it compile.

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

template<class K, class V>
class LruCache
{
public:
    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()); // placeholder, will be updated after insertion
            auto [new_pos, inserted] = values.emplace(key, std::make_pair(value, order.begin()));
            order.front().it = new_pos; // update the placeholder with new_pos iterator
            if (size() > maxSize)
            {
                values.erase(order.back().it);
                order.pop_back();
            }
        }
        else
        {
            pos->second.first = value;
            if (pos->second.second != order.begin()) // move list node to the front
                order.splice(order.begin(), order, pos->second.second);
        }
    }



    class values_map_iter;
    typedef std::list<values_map_iter> order_list;
    typedef std::unordered_map<K, std::pair<V, typename order_list::iterator>> values_map;
    class values_map_iter
    {
    public:
        values_map::iterator it;
    };

    values_map values;
    order_list order;
    size_t maxSize;
};


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

It's more illustrative to view the diff to understand the change: