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,ac39a12d5faf5b14 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-04-23 12:04:35 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail From: Stephen Leake Newsgroups: comp.lang.ada Subject: Re: Grace and Maps (was Re: Development process in the Ada community) Date: 23 Apr 2002 14:59:57 -0400 Organization: NASA Goddard Space Flight Center (skates.gsfc.nasa.gov) Message-ID: References: <3CB46975.90408@snafu.de> <3CBAFFEE.2080708@snafu.de> <4519e058.0204171036.6f0a7394@posting.google.com> <3CBDD795.4060706@snafu.de> <4519e058.0204180800.44fac012@posting.google.com> <3CBF0341.8020406@mail.com> <4519e058.0204190529.559a47ae@posting.google.com> <3CC1C6B3.6060306@telepath.com> <3CC21747.5000501@telepath.com> <3CC59ED2.1000803@home.com> NNTP-Posting-Host: anarres.gsfc.nasa.gov Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: skates.gsfc.nasa.gov 1019588767 23758 128.183.220.71 (23 Apr 2002 19:06:07 GMT) X-Complaints-To: usenet@news.gsfc.nasa.gov NNTP-Posting-Date: 23 Apr 2002 19:06:07 GMT User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: archiver1.google.com comp.lang.ada:23002 Date: 2002-04-23T19:06:07+00:00 List-Id: "Warren W. Gay VE3WWG" writes: > I'm not sure about this sort requirement. Many applications only need to > fetch a value based upon a key. Requiring that the map be sorted will > probably impose suboptimal performance if your requirement doesn't require > sorting. If they want to fetch a value based on a key, a sorted structure is the fasted way to do that. If they don't want to pay for the sorting overhead on insert, they will pay for the very slow fetch time. What are the _timing_ requirements in general? fetching a value from a non-sorted structure is O(n). Fetching from a sorted structure is generally O(logn), and can be O(1) for an optimal hash table. Just because the user doesn't need a sorted iteration thru the map contents, that doesn't mean they don't want a sorted structure. > The sort requirment could be made as part of iteration, and > optionally at that. This is true; we should allow for different implementations. However, I seriously doubt anyone would implement a non-sorted map for a serious application. -- -- Stephe