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.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,effb80d4bb7716dd X-Google-Attributes: gid103376,public From: Matthew Heaney Subject: Re: Wanted: Ada STL. Reward: Ada's Future Date: 1999/02/01 Message-ID: #1/1 X-Deja-AN: 439267689 Sender: matt@mheaney.ni.net References: <790f4q$3l@bgtnsc01.worldnet.att.net> <7931ej$qqf@bgtnsc02.worldnet.att.net> NNTP-Posting-Date: Sun, 31 Jan 1999 22:27:48 PDT Newsgroups: comp.lang.ada Date: 1999-02-01T00:00:00+00:00 List-Id: "Alexy V Khrabrov" writes: > Matthew Heaney wrote in message ... > > >On the contrary, a set is next-to-useless as a collection abstraction in > >any real program. > > > On the contrary, set is a useful abstraction. In fact, it's the first > abstaction in mathematics, used by Euclid to prove that the SET of primes is > infinite. I don't care about mathematics or Euclid. I care about writing real computer programs that have to meet real deadlines. > Set is a part of C++ STL which is used all the time, and emphasized in all > STL books. > I've seen a gazillion programs using lists for mimicing set behavior, and > will see a bazillion more. Then the STL has invented an abstraction I'll probably never use. The STL is not a good model for an Ada components library, anyway. > >A set is an unordered collection without duplicates. > > Not necessarily unordered. A very useful extension of math set is a set of > ordered items, for which a generic taking an "<" parameter along with the > Element type and "=" is most suitable form in Ada. Ah, but there's the rub. From a semantic point of view, a set is unordered, even if it has an implementation that is ordered. The reason you have to order the items (internally) is because the set is being used to ... implement a computer program! Requiring that the items have a comparison operator is in fact exposing an implementation detail, a detail that only manifests itself because you have to pay attention to space & time semantics too. If you need an unordered collection without duplicates, then by all means use a set, and import a comparison operator if necessary (always a good idea, actually). But if you need just an unordered collection, and duplicates are acceptable, then do NOT use a set, use a container. > And I do require sets, as many other people do, too. Real world contains > sets, and any faithful OOP will need them. Funny, I've been programming for over 10 years, and I've NEVER needed an unordered collection without duplicates (i.e. a set). But there have been MANY times when I needed an unordered collection with duplicates (i.e. a container). Most of the time you just want to stuff something into a collection so you can remember it for a little while, without incurring any insertion overhead. When we were using the old Booch Components, I NEVER used the Set packages, because I never had a use for them. What happens is that the programmer looks in his components library, doesn't see what he needs, and instead of writing a high-level container, uses a low-level linked list to implement his collection. This is all wrong, because a linked list is at the wrong level of abstraction. > I prefer ordered sets whenever I can supply the "<" -- and I almost always > can. Give me one example where you can't. I can even sort files on their > last access time, can't I? Tasks on their name, etc. -- even limited > private types, that is. I use sets when I need an unordered collection without duplicates (which almost never need). I use containers when I need an unordered collection with duplicates (which I almost always need). > >In my work on the ACL (which I suspended until gnat 3.11p came out: it > >wouldn't compile otherwise), I call this kind of abstraction a > >"container." There is only a minimal set of operations on a Container > >type: > > > >o add an item to the container > > > >o iterate over items in the container > > > >o remove the item currently designated by an (active) iterator > > > Where is your ACL? Is it public? It will be made public as soon as some caring person ports gnat 3.11p to LinuxPPC. If I could only convince Robert Dewar to get himself a nice Mac... > >The first thing in the morning you need a Container, not a Set. > > Well, and I need sets, buddy! That, and a big cup of coffee...