From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f2690a5e963b61b6 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!postnews.google.com!g14g2000cwa.googlegroups.com!not-for-mail From: "MMM" Newsgroups: comp.lang.ada Subject: Re: GCC 4.0 Ada.Containers Cursor danger. Date: 11 Jul 2005 07:57:48 -0700 Organization: http://groups.google.com Message-ID: <1121093867.964444.232420@g14g2000cwa.googlegroups.com> References: <1120474891.635131.216700@g44g2000cwa.googlegroups.com> <1120575076.876798.108220@g44g2000cwa.googlegroups.com> <1120583470.429264.325450@g43g2000cwa.googlegroups.com> <42cb8d21$0$22761$9b4e6d93@newsread2.arcor-online.net> <42cd064c$0$10817$9b4e6d93@newsread4.arcor-online.net> <42cda8c4$0$22780$9b4e6d93@newsread2.arcor-online.net> <1u3hh2597i4ne$.1ryetugksbmus.dlg@40tude.net> <1120834341.499757.133770@g43g2000cwa.googlegroups.com> NNTP-Posting-Host: 168.159.190.36 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-Trace: posting.google.com 1121093873 16906 127.0.0.1 (11 Jul 2005 14:57:53 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Mon, 11 Jul 2005 14:57:53 +0000 (UTC) In-Reply-To: <1120834341.499757.133770@g43g2000cwa.googlegroups.com> User-Agent: G2/0.2 Complaints-To: groups-abuse@google.com Injection-Info: g14g2000cwa.googlegroups.com; posting-host=168.159.190.36; posting-account=0PrGnQwAAAAhG4fw_pPdaColajHpyOJW Xref: g2news1.google.com comp.lang.ada:11997 Date: 2005-07-11T07:57:48-07:00 List-Id: 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