The "oh no, set elements are const but it's because the internals of the set objects are used to sort"-problem is as old as the STL. This has nothing to do with modern C++. The whole article is sub par because it describes a C++98 effect and tries to put a modern C++ spin on it. It doesn't discuss good and valid solutions of this problem, which is fundamentally about data structures, and it does not mention the mutable keyword. I liked the quote in the end though.
While I like that the article introduces a new concept from C++17, namely the `extract()` member, I think the article is misnamed: it only deals with weird & buggy behaviour that you get when incorrectly dealing with associative containers. This is not restricted to C++, though, and I would summarize the main message as:
"Take care when changing that over which you iterate"
That is something notably different than claiming that these are the 'Worst bugs' you could find...
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 iterating over the same item more than once in a rather random fashion?
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().
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).
8 comments
[ 2.8 ms ] story [ 38.9 ms ] threadAnd on a similar note, OP is talking about changing data types, PLAN THIS OUT BEFORE DOING YOUR REGRESSION ALGORITHM.
Sorry for the caps, but hope someone can save a week or 2 of effort.
But I agree in general terms: changing data types should not be done lightly :-)
"Take care when changing that over which you iterate"
That is something notably different than claiming that these are the 'Worst bugs' you could find...
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().
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