Re: GCC 4.0 Ada.Containers Cursor danger.

["MMM" <terekhov@emc.com>]

Matthew Heaney wrote:
>
> MMM wrote:
>
>>Exactly. But the original claim was that "unordered" containers do not
>>exist.
>
>
> It depends of course on how one defines "unordered."
>
> I use the term "unordered" to refer to a set (or map) implemented using
> some kind of sequential container (a list, say).  The only way to find
> an element is by performing a linear search.
>
> An "ordered" set is implemented using a data structure that allows you
> to find an element in better than O(n) time.  Using that criterion,
> then both the Hashed_Set and Ordered_Sets are "ordered."
>
> The order isn't specified for a Hashed_Set, but its elements aren't
> organized willy-nilly either (qua list).  A hashed container is
> implemented using a hash table, and so its time complexity is O(1), and
> it is in that sense that I refer to a hashed container as being
> "ordered."

Ok, then you need to convince the rest of the world that your
definition
of "order" through the time complexity and big-O notation makes sense.
To understand what is wrong with you definition you could start at
http://en.wikipedia.org/wiki/Order
It could really help.

>
> Part of the confusion stems from the fact that other languages like C++
> use the term "sorted" to refer to what the Ada standard calls
> Ordered_Maps and Ordered_Sets.  (My original API actually used the
I don't think that "Sorted" vs. "Ordered" brings much confusion. What
is
confusing is that such a specialized cases as "Ordered_Maps" and
"Ordered_Sets" has been put as a foundation of the standard library.

> terms Sorted_Maps and Sorted_Sets.)  The "sorted vs. hashed"
> nomenclature probably makes it less confusing to say that the
> associative containers are both "ordered," but it's not that big a deal
> as long as we know we're refering to associative containers, and
> understand that a hashed container has some order, but that its order
> isn't specified.
>
Sorry, can't decifer this last sentence. Compating sorted vs. hashed is
like apples vs. oranges.