C++:我可以重用/移动 std::list 元素从中间到结尾吗？

Question

我正在优化 LRU 缓存实现的常数因子，我使用 std::unordered_map 将 ::iterator 存储到 std::list，即使附近的元素被添加或删除，它们也保证保持有效。这导致 O(n) 运行时间，因此，我将追求常数因子。

我知道每个迭代器基本上都是指向保存我的东西的结构的指针。目前，为了将给定元素移动到链表的后面，我用迭代器调用 l.erase(it)，然后分配一个新的对 w/make_pair(key, value ) 到 l.push_back() 或 l.emplace_back() (不太确定区别)，并获取新的迭代器以插入到 map 带 prev(l.end()) or --l.end() .

有没有办法重新使用现有的迭代器和它指向的底层双向链表结构，而不是像上面那样每次都销毁它？

(我的运行时间目前是 56 毫秒(超过 99.78%)，但 leetcode 上最好的 C++ 提交是 50 毫秒。)

Answer 1

正如 HolyBlackCat 指出的那样，解决方案是使用 std::list::splice。

l.splice(l.end(), l, it);

这避免了任何需要 l.erase、make_pair()、l.push_back/l.emplace_back()，以及获取 prev(l.end())/--l.end() 以更新底层 std::map.

遗憾的是，虽然它并没有带来更好的运行速度，但是，哦，好吧，可能是测量变化，或者是使用更专业的数据结构的实现。

更新:实际上，我修复了重用 l.begin() 中“已删除”元素的最终实例，并获得了 52 毫秒/100%! :-)