Круглая зависимость, где два контейнера хранят итераторы для элементов друг друга ⇐ C++

[Anonymous]

Я написал быстрый импл кэша LRU, где все данные (например, клавиша -> пары значений) хранятся в неупорядоченной карте, а список заказов просто сохранял указатели на эти элементы. Однако с C ++ у меня есть проблема здесь: < /p>

Код: Выделить всё

template
class LruCache
{
public:
typedef std::unordered_map values_map;
typedef std::list order_list; // list of iterators into values_map
};
< /code>
Однако мне также необходимо сохранить ссылку на узел в списке внутри карты. Не проблема, итератор в список заказов может быть добавлен на карту: < /p>
typedef std::unordered_map values_map;

Вот где он становится сложным: valive_map теперь изменяется, что делает его несовместимым с order_list , которые не могут хранить итераторы в значениях values_map .
Эффективно, теперь существует циркулярная зависимость. Реструктуризация макета данных, например. Список должен содержать только указатели/итераторы в карте.

Код: Выделить всё

#include 
#include 
#include 

template
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(pos2.first); // ERROR
if (size() > maxSize)
{
values.erase(reinterpret_cast(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 values_map_;
typedef std::list order_list; // values are values_map::iterator
typedef std::unordered_map values_map;

values_map values;
order_list order;
size_t maxSize;
};

int main()
{
LruCache test;

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

Я помеченные места проблемы с ошибкой Comment и для того, чтобы заставить его использовать Reinterpret_cast, чтобы сделать его компиляцией (примечание, GCC жалуется на там).
Когда я попросил Deepseek решить зависимость, чтобы схема сохранена в этом режиме (я должен был прервать его, иначе Типы):


Подробнее здесь: https://stackoverflow.com/questions/794 ... rs-elememt