Re: [Boost-users] Correct use of unordered_map

Subject: Re: [Boost-users] Correct use of unordered_map
From: Daniel James (daniel_james_at_[hidden])
Date: 2009-09-03 02:50:28

2009/9/2 John Dlugosz <JDlugosz_at_[hidden]>:
>
> 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