Re: GCC 4.0 Ada.Containers Cursor danger.

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

Matthew Heaney wrote:

>
> Dmitry A. Kazakov wrote:
>
>> On Fri, 08 Jul 2005 13:15:26 GMT, Matthew Heaney wrote:
>>
>> But sets and maps are unordered containers.
>
>
>
> This is silly.  We are talking about the Ada 2005 standard container
> library.  In that library, of course sets and maps *are* ordered.
>
That is not silly at all. And there is not such a library as the Ada
2005 standard container library yet. There is the candidate or proposal
if you wish. And the fact that in that proposal 'of course sets and
maps *are* ordered' is silly indeed. The reason is that, if one
remember some mathematics, having an order is a fundamental property
that distinguish vectors and lists on the one side and sets and hashes
on the other. Another silliness is overgeneralization of the
'iterrator' concept and renaming it to 'cursor'. Yet another silliness
is the terminology used - Vectors, Lists, Ordered_Sets, Hashed_Sets,
Hashed_Maps, Ordered_Maps.
The problem here is that this terminology doesn't reflect the
fundamental differences between these types and mixes underlying
mathematical conncepts in some unregular way. This unnecessarily
complicates and hides underlying principles. And the principles are
very simple:

 - if a container has an order property, then it is either list or
vector, if not, then it is either set or hash.
 - if a container is a mapping, then it is either vector or hash, if
not, then it is either list or set.

Then the basic types could be:

 List - a container that provides ordering, but no mapping from it's
elements to any kind of index or position by default.

 Vector - a container that provides ordering and mapping from some kind
of index to it's elements. The only general requirement to this index
is that it should be ordered, i.e. comparison operations should be
defined for it.

 Set - a container that provides neither order nor mapping to any
index.

 Hash - a container that provides no ordering, but provides a mapping
from some kind of key to it's elements. The only general requirement to
this key is that it should be possible to calculate a hash from it's
value somehow.

These four concepts form an ortogonal normal basis for the container
types. Everything else is a specialisation or/and mixture of these
basic concepts. Of course internal implementation of all of these basic
types can use whatever ordering or indexing algorithms that could
provide reasonable implementation. Unfortunately the current proposal
uses some kind of "mixture" of these basic concepts or non ortogonal
basis. This unnecessarily distances current proposal from underlying
theory and complicates understanding of relations between different
concepts.

It would be very sad if the final standard would contain such a mixture
of concepts.

>
..... skip .....

>
>> What is the common
>> denominator across all container types? There seems to be none.
>
>
No, it is not none! If we look at these basic types, then we will see
one fundamental thing about containers. Namely, the only two elementary
operation that has common semantic among all container types are
'iteration' over their elements and membership test. Everything else is
 either has container specific semantics or has no natural semantics at
all for some container types. So, the common denominator across all
container types is:
    a) They all contain some kind of elements
    b) They all have a concept of 'iterating' over their elements
       in an unspecified order.
    c) They all have membership test.
    d) Provide similar interface with slightly differnt semantics
       for an element addition and deletion.

>
> Vectors and lists are "sequence" containers, that allow you to
> explicitly specify the position.

Not exactly. The common property of vectors and lists is that they are
"ordered" somehow and you can sort them by some criteria.
The difference is that vector elements could be directly accessed using
some kind of index and lists provide only sequential access (like
direct_io and sequential_io).

>
> Sets and maps are "associative" container, that positions elements in
> key order.  (A sorted order for "ordered" containers, and a hash order
> for "hashed" containers.)

Again, this mixture of basic properties, namely 'ordering' and
'mapping', is very unfortunate.

>
> All containers have a consistent mechanism for iterating over elements.
>
Exactly.

Mikhail