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=-2.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM, MAILING_LIST_MULTI autolearn=unavailable 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!news3.google.com!news2.google.com!proxad.net!usenet-fr.net!news.enst.fr!melchior!cuivre.fr.eu.org!melchior.frmug.org!not-for-mail From: Duncan Sands Newsgroups: comp.lang.ada Subject: Re: Ada.Containers.Vectors - querying multiple elements Date: Tue, 26 Apr 2005 18:00:11 +0200 Organization: Cuivre, Argent, Or Message-ID: References: <1114515832.32583.41.camel@localhost.localdomain> <426E5A0B.3010109@on2.com> NNTP-Posting-Host: lovelace.ada-france.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: melchior.cuivre.fr.eu.org 1114531230 67480 212.85.156.195 (26 Apr 2005 16:00:30 GMT) X-Complaints-To: usenet@melchior.cuivre.fr.eu.org NNTP-Posting-Date: Tue, 26 Apr 2005 16:00:30 +0000 (UTC) Cc: comp.lang.ada@ada-france.org To: users@charles.tigris.org Return-Path: In-Reply-To: <426E5A0B.3010109@on2.com> X-Mailer: Evolution 2.2.1.1 X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at ada-france.org X-BeenThere: comp.lang.ada@ada-france.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Gateway to the comp.lang.ada Usenet newsgroup" List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Xref: g2news1.google.com comp.lang.ada:10721 Date: 2005-04-26T18:00:11+02:00 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. > > I've been playing around with Ada.Containers.Vectors (part of > > Ada 2005, see http://charles.tigris.org/; look for AI-302) and > > noticed that there's no way to view or operate on a "slice" of > > a vector. > > There's nothing special about a vector, that it alone should provide > array-based operations. A vector is a container just like any other, > but with constant time (O(1)) random access. That is presumably how you like to think of it, but you could also say: "A vector is a container just like any other, from which you can take slices with O(length) time". > 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 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. > 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? > > I'd like something like this: > > > > procedure Query_Elements > > (Container : in Vector; > > First_Index : in Index_Type; > > Last_Index : in Extended_Index; > > Process : not null > > access procedure (Elements : in Element_Array)); > > > > where Element_Array would be: > > > > type Element_Array is > > array (Index_Type range <>) of Element_Type; > > > > Is there any reason no such routine exists? > > This wouldn't work, because a vector container doesn't guarantee that > the underlying data structure is a contiguous array. As you mention below, it can be implemented by copying into a buffer (read-only access), or copying to and from a buffer (read-write access). So there is no logical objection, though limited stack space might be a practical problem. > > It would be good to have for both > > efficiency reasons > > No, there would be no efficiency benefit (in fact, there would be an > efficiency penalty, in order synthesize an array object) if the > underlying data structure were something other than an array. Surely the question is whether it can be significantly more efficient to implement it in the body, as compared to having the user do an element by element copy. For the pointer-to-an-array implementation, the body can do a much more efficient job; I don't know how much you gain for deques and skip lists. > > and simple implementation of certain classes of algorithms. > > In my case I have a "divide and conquer" recursive algorithm which while it > > can be written using the current package, would be simpler to write if something > > like Query_Elements existed. > > The thing I wish the API provided for vectors are operators such as: > > function "+" (C : Cursor; Off : Integer) return Cursor; > function "-" (L, R : Cursor) return Integer; > etc. > > I lobbied for this, but there was little enthusiasm among the ARG. OK. All the best, Duncan.