3 ms·

So the fix is to remove the item and reinsert it into the structure while iterating over it. Doesn't this mean that it could very well happen that you'll end up

• deleted 8y ago
  [deleted]
• mannykannot 8y ago
  I think you have a point here, not for the vector version (though the resulting vector may not be sorted), but for the insert-then-erase and extract-then-insert versions (though the author does not have complete solutions for the original problem using these approaches). The erase() method invalidates iterators to the erased element, but returns an iterator to the next one. If you resume iterating with that, there is the possibility of finding the updated Employee again. Extract() also invalidates iterators, but does not return one. If, as in the example, you use the iterator returned by insert() to resume iteration, you may skip over some eligible employees. If you use iterator++ in the extract() call (if that's not undefined behavior), you will presumably be in the same situation as using the iterator returned by erase().
• voidmain 8y ago
  Yes, the "fixed" (multimap) version looks to have the Halloween Problem [1]. As this illustrates, const correctness is no substitute for understanding of iterator invalidation and data structure invariants in C++. As another example, the original code could have been writted with a multiset< unique_ptr< Employee > > and a suitably modified comparator and not required any const casting to have the same undefined behavior as the original (you can access a mutable object through a const unique_ptr). [1] https://en.wikipedia.org/wiki/Halloween_Problem https://en.wikipedia.org/wiki/Halloween_Problem