Re:The true cost of linked lists
by gpderetta on Monday June 06, 2022 @03:29PM
(#31644906)
In c++, std::deque is better than std::list as an address preserving backing store as it requires less memory allocations, less space overhead and objects will be closer together.
[ Parent
| on HN ]
Re:The true cost of linked lists
by deathanatos on Monday June 06, 2022 @05:14PM
(#31646356)
> std::deque is better than std::list as an address preserving backing store
std::deque will invalidate iterators in some cases. Since my example above was an LRU cache, the cache's removal of an item from the middle of the list (to shift it to the end) is one of those actions that would invalidate iterators in a std::deque.
(Not to malign std::deque: it is a useful datastructure in its own right, and if you need queue-like semantics (e.g. cheap remove from front), it's a better choice than a LL, and both are better than vectors for that purpose. I find deque's internals to be a bit weird … my goto would normally be a ringbuffer, but the STL provides deque instead, so eh, it's good enough, if a bit odd IMO.)