4 ms·

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:

• gpderetta 4y ago
  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.
  • deathanatos 4y ago
    > 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.) (Cf. https://en.cppreference.com/w/cpp/container/deque https://en.cppreference.com/w/cpp/container/deque)