C ++：我可以从中间到结尾重用/移动std :: list元素吗？ [英] C++: can I reuse / move an std::list element from middle to end?

问题描述

我正在优化我的LRU缓存实现的常量因素，我使用 std :: unordered_map 来存储 :: iterator s到 std :: list ，即使在添加或删除附近元素时也保证有效。这导致O（n）运行时，所以，我正在追求常数因子。

I'm optimising constant factors of my LRU-cache implementation, where I use std::unordered_map to store ::iterators to std::list, which are guaranteed to remain valid even as nearby elements are added or removed. This results in O(n) runtime, so, I'm going after the constant factors.

我知道每个迭代器基本上都是指向保存我的结构的指针东西。目前，要将给定元素移动到链表的后面，我使用迭代器调用 l.erase（it），然后分配一个新对w / make_pair（键，值）到 l.push_back（）或 l.emplace_back（）（不太确定区别），并将新的迭代器重新插入到地图中，并带有 prev（l.end（））或 - l.end（） 。

I understand that each iterator is basically a pointer to the structure that holds my stuff. Currently, to move a given element to the back of the linked list, I call l.erase(it) with the iterator, and then allocate a new pair w/ make_pair(key, value) to l.push_back() or l.emplace_back() (not too sure of the difference), and get the new iterator back for insertion into the map w/ prev(l.end()) or --l.end().

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

Is there a way to re-use an existing iterator and the underlying doubly-linked list structure that it points to, instead of having to destroy it each time as per above?

（我的运行时间目前为56ms（节拍99.78％），但leetcode上提交的最佳C ++是50ms。）

(My runtime is currently 56ms (beats 99.78%), but the best C++ submission on leetcode is 50ms.)

推荐答案

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

As pointed out by HolyBlackCat, the solution is to use 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 。

This avoid any need to l.erase, make_pair(), l.push_back / l.emplace_back(), as well getting the prev(l.end()) / --l.end() to update the underlying std::map.

可悲的是，它不会导致更好的运行时速度，但是，哦，可能是测量变量，或者使用更专业的数据结构的实现。

更新：实际上，我修复了从 l.begin（）重用已删除元素的最终实例，得到了52ms / 100％！ ： - ）

Update: actually, I fixed the final instance of reusing the "removed" elements from l.begin(), and got 52ms / 100%! :-)

这篇关于C ++：我可以从中间到结尾重用/移动std :: list元素吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！