Re: [Boost-users] unordered_map documentation (was RE: Correct use of unordered_map)

Subject: Re: [Boost-users] unordered_map documentation (was RE: Correct use of unordered_map)
From: John Dlugosz (JDlugosz_at_[hidden])
Date: 2009-09-04 11:39:53

> Sorry, I don't see what you're getting at. As far as I know, STL
> ranges are the same as they've alway been (two iterators defining a
> half-open range).

In my earlier post which started this particular sub-discussion, I was trying to describe how to iterate a collection without any ordering.  A "range" is two points in an ordered list.  Now, we're focusing on describing an internal ordering, so don't worry about that.

> 
> > Reading it through from the beginning...
> 
> In the future, can you include the url or path of the page you're
> referring to? It'd make it a lot easier.

Yes.

> 
> > "An unordered associative container that associates unique keys with
> another value."
> >
> > Key has equivalence relation (only).
> 
> To be pedantic, they might have other relations. Perhaps, 'The only
> required relation is an equivalence relation'.
> 

Yes.

> > member begin returns "An iterator referring to the first element of
> the container"
> >
> > "first" contradicts "unordered".  There is no meaning for first.
> 
> Not really. In this context, unordered means that the order of
> elements doesn't follow a predetermined order, and can change under
> certain conditions. There is a first element, but it isn't
> deterministic.
> 

Ah, here is where we differ.  You know what it is supposed to mean; e.g. how the container actually works.  But that's not what it says.  I started from the top of the document -- there is no context that establishes this.  That is what I suggested adding.  In any case, why not make it clearer and better?  My published magazine articles have always been much improved by circulating a first draft and getting back comments, especially where some point was unclear to someone but I "knew" what it was putting it in.

> I don't think the standard explicitly says so. It does state that
> rehashing changes the order, I'm not sure if that implies that the
> order remains constant under all other conditions. If a container
> tracked the existence of iterators I don't know if it could change the
> order of elements when there are no existing iterators. You'd probably
> get a more informed answer on comp.std.c++ or comp.lang.c++.moderated.
> I'm not much of a language lawyer.

The hash function is the only place in unordered_map.htm where "order" is mentioned at all.  As it stands, it's also a non sequitur like "begin", since this is "an unordered associative container".  (I am something of a language lawyer, BTW)

> 
> > (BTW, the HREF to n2691 is dead)
> 
> Thanks, I'll fix that. I should probably change the wording as well as
> that version is now out of date. Although I don't quite conform to the
> latest version - and I'm not going to catch up until the version
> without concepts is released.

Personally, I'm more interested in how it may differ from the implementation that Microsoft supplies in Visual Studio 2008's update (I presume it is from Dinkumware), then in the ideal that no compiler supports yet.  That's my engineering interest for work, anyway.  

> 
> > To suggest a concrete example, you might insert, "Although no
> relation is supplied for the key type, for purposes of iteration the
> elements will appear to have a definite order that is determined by the
> implementation.  This order may be changed by any function that
> invalidates iterators, including insert and rehash."
> 
> I think I'd write 'Although no ordering is supplied for the key type'
> since there's an equivalence relation.

Yes, I tend to forget that "relation" does include the equivalence, since I normally see and use "equality operator ...(later)... relational operations" as separate parts.

> There isn't much freedom. It might be possible to use another
> structure and fake the buckets. Although that would be pretty dubious.
> 
> Intersetingly, I don't think there's a requirement that the iteration
> order corresponds to the buckets - it isn't specified that local
> iterators and normal iterators have to follow the same order. Although
> it is required that equivalent keys are adjacent in unordered_multimap
> and unordered_multiset.
> 
> Daniel

I wonder, why are "local iterators" and buckets exposed at all?  A non-order-preserving (experimenting with alternative to "unordered" that better describes the situation--in Perl for example they point out that the order of keys is not the order in which you added them, but they don't feel the need to explain that they are not sorted either) associative container doesn't *need* that to work.  I pretty much ignored their existence.

--John

TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.