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:

#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):

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./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):

• c++
• stl
• lru

• Please provide an minimal reproducible example where you use the std::list. – Thomas Matthews Commented Mar 11 at 0:23
• How do you determine Least Recently Used? Where's the code to drop the LRU item and insert the new item? – Thomas Matthews Commented Mar 11 at 0:36
• added sample code. LRU is just an example, don't try to fix LRU :) I'm curious how to fix the dependency! – Pavel P Commented Mar 11 at 0:39
• 1 there's always std::any ... i think most implementations give you at least 2 pointers of SBO – Ahmed AEK Commented Mar 11 at 0:51
• 1 Circular dependency where two containers store iterators to each other's elememts This question itself is not the right one to ask, you should NEVER store iterators they're supposed to be short lived view objects. If you have circular dependency between datastructures replace it with one new one you write yourself. – Pepijn Kramer Commented Mar 11 at 3:34

1 Answer 1

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

https://godbolt./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: