C++：我可以重用/移动一个 std::list 元素从中间到最后吗？
C++: can I reuse / move an std::list element from middle to end?
我正在优化我的 LRU 缓存实现的常数因子，我使用 std::unordered_map 将 ::iterator 存储到 std::list，即使在附近也保证保持有效添加或删除元素。这导致 O(n) 运行时间，因此，我将追求常数因子。
我知道每个迭代器基本上都是指向保存我的东西的结构的指针。目前，为了将给定元素移动到链表的后面，我用迭代器调用 l.erase(it)，然后分配一个新对 w/ make_pair(key, value) 到 l.push_back() 或 l.emplace_back()（不太确定区别），然后取回新迭代器以插入到带有 prev(l.end()) or --l.end().
的映射中
有没有办法重新使用现有的迭代器和它指向的底层双向链表结构，而不是像上面那样每次都销毁它？
（我的运行时间目前是 56ms（超过 99.78%），但 leetcode 上最好的 C++ 提交是 50ms。）
正如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() 中的 "removed" 元素的最终实例，并获得了 52 毫秒/100%！ :-)
我正在优化我的 LRU 缓存实现的常数因子，我使用 std::unordered_map 将 ::iterator 存储到 std::list，即使在附近也保证保持有效添加或删除元素。这导致 O(n) 运行时间，因此，我将追求常数因子。
我知道每个迭代器基本上都是指向保存我的东西的结构的指针。目前，为了将给定元素移动到链表的后面，我用迭代器调用 l.erase(it)，然后分配一个新对 w/ make_pair(key, value) 到 l.push_back() 或 l.emplace_back()（不太确定区别），然后取回新迭代器以插入到带有 prev(l.end()) or --l.end().
有没有办法重新使用现有的迭代器和它指向的底层双向链表结构，而不是像上面那样每次都销毁它？
（我的运行时间目前是 56ms（超过 99.78%），但 leetcode 上最好的 C++ 提交是 50ms。）
正如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() 中的 "removed" 元素的最终实例，并获得了 52 毫秒/100%！ :-)