Re:The true cost of linked lists
by verall on Monday June 06, 2022 @11:15AM
(#31641557)
This is exactly correct, since at least in C++, adding elements to any other data structure can invalidate the stored iterators/references in your hashmap. std::list will mean you pay a slight cost when adding new entries, which if your cache is working is hopefully not so often, or the malloc is already dominated by whatever is being cached.
[ Parent
| on HN ]
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.
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.)