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,1fa85f3df5841ae1 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news4.google.com!news.glorb.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local01.nntp.dca.giganews.com!nntp.megapath.net!news.megapath.net.POSTED!not-for-mail NNTP-Posting-Date: Wed, 27 Apr 2005 19:51:49 -0500 From: "Randy Brukardt" Newsgroups: comp.lang.ada References: <1114515832.32583.41.camel@localhost.localdomain><426E5A0B.3010109@on2.com> Subject: Re: Ada.Containers.Vectors - querying multiple elements Date: Wed, 27 Apr 2005 19:54:09 -0500 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4927.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4927.1200 Message-ID: <-ICdneu9IoY7ru3fRVn-3Q@megapath.net> NNTP-Posting-Host: 64.32.209.38 X-Trace: sv3-FmPDa5V9QwyiF9pVI/O2GjLH26Iilhe9HGLt7E4gKoqwvJ3wrbsoju4AWeBllVa44LfMaJR+seUWHzj!Af4DVT2ubcobtIkJDwWcXSacNV9/ihPkfapx99ixICyBk0VY5qorG6xWUhQra4QjWZkfWrtRHqqG X-Complaints-To: abuse@megapath.net X-DMCA-Complaints-To: abuse@megapath.net X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.32 Xref: g2news1.google.com comp.lang.ada:10768 Date: 2005-04-27T19:54:09-05:00 List-Id: "Duncan Sands" wrote in message news:mailman.79.1114531228.24457.comp.lang.ada@ada-france.org... > Hi Matthew, to summarize your reply: "that's the price you pay for > abstraction". What I would really like to know is why there is a > significant advantage to allowing implementations that are far from > the pointer-to-an-array method. Probably because it wouldn't have gotten enough support from the ARG without an appropriate level of abstraction. There is a political aspect to designing for an existing standard, after all, you don't always end up with what someone might think is the best possible solution. In our case, the way our generics are implemented (always shared bodies), the "canonical" implementation would require thousands of tiny allocations. That would work, of course, but it would hardly be high speed. By allocating smaller chunks (and avoiding copying to/from those chunks), we can keep those allocations down to something that is done only for the elements that make up an expansion. ... > > The logical model for a vector is an array, but physically a vector can > > have any representation consistent with logical specifications. > > Sure, but that's not a restriction on the specification, that's a > restriction on the implementation. You could add a procedure like > I mentioned to the spec - the implementations would have to implement > it, that's all. The question is: what do you lose by adding such a > routine? I fully appreciate that finding the "right" abstraction is > a delicate balancing act requiring a lot of time and experience. So: > why is the current specification the right choice, and not one with > "slices" in it. For example, Ada.Strings.Unbounded has slices - was > that a mistake? The slices of Ada.Strings.Unbounded are copies, always. I don't think there would be any problem with having a slice function -- it just would be rather inefficient. > > The reference implementation uses an array, but I know of a vendor who > > plans to use a skip list, and another who plans to use a two-level > > structure (not unlike an STL deque). > > To my mind, this is the real argument. It implicitly shows that there > can be real advantages to implementing Vector in a non-obvious way. > However I don't see why either of these is incompatible with taking > read-only slices. It may not be as efficient as with a simple > pointer-to-array implementation, but it's not bad: the deque is no > problem, and the skip list should be pretty efficient too. That's > fairly inevitable: if you can access elements in constant time, you can > access N of them in time O(N). However it looks to me like in both > cases the "slice" operation can be done more efficiently than by > repeatedly calling "Element" to copy into a buffer. A slice is a *contiguous* list of elements in every compiler that I'm familiar with. If you have a non-contiguous representation (certainly the case with a skip list or deque), the only way to provide that would be a full-scale copy. (One could optimize it if it happened to be all within a single chunk, but that seems unlikely to be of much benefit.) > > So there are no array-based operations for vector, just as there are no > > array-based operations for any other container. > > What's wrong with having operations that only apply to a vector and not > to other containers? I guess you have a philosophy that tells you it is > a bad idea - care to explain? We really wanted the Vector and List to be interoperable as much as possible, and similarly for the Map and Set. We've tended to add operations to the "other" container to make that possible. (In theory, you could have an interface that would allow algorithms to work on both a Vector and a List. That probably would be more valuable if there were more types of sequence containers.) There are of course operations on one that isn't allowed on the other. But I have little enthusiasm for making Vectors even larger; it already has 240 paragraphs. (Useless aside: When I first started formatting the containers library for the draft AARM, I just dumped the entire text into the source file, with no section breaks. It generated about 1200 paragraphs. I was impressed that the tools didn't expire when given that many paragraphs at once. I'm rather glad to not have to refer to A.18.2(1188/2). :-) Randy Brukardt.