我正在优化 LRU 缓存实现的常数因子，我使用std::unordered_map储藏::iterators to std::list，即使添加或删除附近的元素，它们也保证保持有效。这会导致 O(n) 运行时间，因此，我将追求常数因子。
我知道每个迭代器基本上都是一个指向保存我的东西的结构的指针。目前，要将给定元素移动到链表的后面，我调用l.erase(it)使用迭代器，然后分配一个新的对 w/make_pair(key, value) to l.push_back() or l.emplace_back()（不太确定区别），并获取新的迭代器以插入到映射中prev(l.end()) or --l.end() //stackoverflow.com/a/51235853/1122270.
有没有办法重用现有的迭代器及其指向的底层双向链表结构，而不是像上面那样每次都销毁它？
（我的运行时间目前是 56 毫秒（超过 99.78%），但 leetcode 上最好的 C++ 提交是 50 毫秒。）
正如所指出的圣黑猫 //stackoverflow.com/users/2752075/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.
Sadly, though, it doesn't result in a better runtime speed, but, oh well, possibly a measurement variation, then, or an implementation using more specialised data structures.
更新：实际上，我修复了重用“已删除”元素的最终实例l.begin()，并得到 52ms / 100%！ :-)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
