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-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-11 16:23:52 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!newsmi-us.news.garr.it!newsmi-eu.news.garr.it!NewsITBone-GARR!fu-berlin.de!uni-berlin.de!ppp-1-91.cvx1.telinco.NET!not-for-mail From: "Nick Roberts" Newsgroups: comp.lang.ada Subject: Re: List container: Insert and Delete Date: Sun, 11 Nov 2001 23:34:18 -0000 Message-ID: <9sn4qk$13g29j$1@ID-25716.news.dfncis.de> References: <3BECA3B7.5020702@telepath.com> <9sjf4n$odm$1@news.huji.ac.il> <9sjkc7$145mhb$1@ID-25716.news.dfncis.de> <3BEDACC0.9A314B54@acm.org> <9sktgm$134npc$3@ID-25716.news.dfncis.de> <3BEEB766.B50C969@acm.org> NNTP-Posting-Host: ppp-1-91.cvx1.telinco.net (212.1.136.91) X-Trace: fu-berlin.de 1005524629 37226803 212.1.136.91 (16 [25716]) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Xref: archiver1.google.com comp.lang.ada:16310 Date: 2001-11-11T23:34:18+00:00 List-Id: "Jeffrey Carter" wrote in message news:3BEEB766.B50C969@acm.org... > Positive integers are generally used to indicate positions in lists in > mathematical notation. For a software list implemented using pointers > (an unbounded list), using integers to indicate positions becomes an > O(N) time operation for every reference to the list. It is better to > abstract the concept of a position to something that provides the same > behavior but with O(1) time complexity. I know it sounds like a good idea, but I don't think it is in reality. Just look at all the messing around that has to be done, with pointers to check you don't delete this, or to check you don't try to access something after deleting it. It's just not worth it. It's all very well saying access will be O(N), but that ignores the fact that chasing down a linked list of pointers is a fast operation (because each step is very simple). In practice, using integers to index positions gains you: simplicty for the user; simplicity for the implementor. With short lists, it's likely to be the most efficient possible implementation anyway. > > However, I'm pretty sure that trying to do insertions and deletions while > > iterating through a list fails both (a) and (b) miserably. That's what I was > > trying to get across. > > I agree that one should not be doing insertions and deletions while > iterating over a list. Iterators should not allow this, and positions > should generally not be used for iteration. Your delicate distinction between an 'iterator' and a 'position' is a little silly. The reasons why it should not be done with iterators are the same as the reasons why it should not be done with positions. I have prepared a proposal, which I am e-mailing to Ted Dennison today for posting on his web site (which he has kindly agreed to). It defines an abstract list with a big set of operations. In it is an inner package which defines an 'unbounded' list type, for which I hope to produce a sample implementation (based on the classic double linkage model). Then I will add a (generic) child package with a 'bounded' list type, for which I will produce an implementation (based on a fixed-size array). The indexed operations will, of course, be of O(1) for the bounded list, yet being both based on the abstract list type, they will be algorithmically interchangeable. So there is a deeper reason for my insistence on indexed operations: I am trying to make a bigger plan 'come together'. Finally, my proposal includes all the usual head and tail dicing operations. Chopping off, or adding on, one item to either end of a list will be the most frequently used operations anyway, for which arguments about indexing don't apply. The indexed operations are mainly there for convenience. As I showed in an example in another thread, really serious manipulations of lists are best done sequentially. I hope you will look at my proposal, and perhaps be a little more convinced! -- Best wishes, Nick Roberts