2009/9/2 John Dlugosz
So the key would be a suitable definition for a "valid iterator". Each iterator for an "unordered" collection that nevertheless can proceed to end() is logically a state that contains a current element and a set of future to-be-traversed elements. Stepping will select one element from that remaining set, and produce an iterator with that as the current element and the future set reduced by that element. Erasing an element removes it from all outstanding iterator's future sets, if present.
Sort of, but you're missing the important point that a range (the STL jargon for what you call set, it's less confusing if we stick to STL jargon) can be defined by two iterators - so not up to the end of the container. If the order of elements changed such that the start iterator was after the end iterator then that range would become invalid which is why the order of elements can't change after an erase.
Inserting an element may or may not add it to the future set each outstanding iterator.
Not sure what you mean there, but remember that insert can invalidate iterators
The future set is not "ordered" and any change might affect which element it picks next, compared to what it would have picked had you not done that. But that does not change the "validity".
Not really, an insert may insert an element after your iterator, an erase may erase the next element - that's the same as the ordered containers. But if your iterators are invalidated (which insert can do, I think the exact conditions are explained in the documentation) you can't use them.
The docs with Boost and with Microsoft's MSDN does not explain it properly. It's just copied from the regular map documentation, and saying it's "unordered" spoils the meaning of the copied phrasing.
Who might I talk to, concerning tightening up the Boost documentation or the ultimate C++ Standard documentation?
I'm the person for the boost documentation. But you should remember that all this documentation assumes familiarity with the STL concepts - which most of what you're talking about comes from. Looking at the documentation it probably could do with a bit more of a discussion of what it means to be 'unordered' but I don't think it's the correct place to document how iterators work - it should be enough to say they're forward iterators and perhaps link to an explanation of what a forward iterator is. Daniel