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.
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?
(My runtime is currently 56ms (beats 99.78%), but the best C++ submission on leetcode is 50ms.)
As pointed out by HolyBlackCat, the solution is to use std::list::splice.
l.splice(l.end(), l, it);
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.
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.
Update: actually, I fixed the final instance of reusing the "removed" elements from l.begin(), and got 52ms / 100%! :-)