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: Daniel James (daniel_james_at_[hidden])
Date: 2009-09-03 16:20:24

2009/9/3 John Dlugosz <JDlugosz_at_[hidden]>:
>> Sort of, but you're missing the important point that a range (the STL
>> jargon for what you call set,
>
> I thought the STL was going to be adopting the "range" concepts from the STL range library.  That is, a range will be a begin-end iterator pair or something that behaves like that.

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).

> 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.

> "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'.

> 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.

> The iterator has a difference type.  It doesn't say what kind of iterator it is, but I assume forward_iterator as the broadest, since input_iterator and output_iterator would not be applicable.
>
> So, do elements have a definite and unchanging order in the container, or can different iterations produce different orders?  The latter gives maximum freedom to the implementation, but is more difficult to define properly.  If the former, just saying that would fix the issues I have with the current definitions.

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.

> (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.

> 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.

> That certainly describes the Boost class.  But should the C++ standard have more freedom?  The draft standard I've seen does include the bucket exposing functions, so maybe it is locked into this one implementation.

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