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-22 15:57:14 PST
Newsgroups: comp.lang.ada
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!nntp.abs.net!uunet!dca.uu.net!ash.uu.net!xyzzy!nntp
From: Jeffrey Carter <jeffrey.carter@boeing.com>
Subject: Re: Grace and Maps (was Re: Development process in the Ada community)
X-Nntp-Posting-Host: e246420.msc.az.boeing.com
Content-Type: text/plain; charset=us-ascii
Message-ID: <3CC48F34.5A474E0F@boeing.com>
Sender: nntp@news.boeing.com (Boeing NNTP News Access)
Content-Transfer-Encoding: 7bit
Organization: The Boeing Company
X-Accept-Language: en
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>
 <a9n0tk$6fs$1@nh.pace.co.uk>
 <4519e058.0204190529.559a47ae@posting.google.com>
 <a9p98h$8hn$1@nh.pace.co.uk> <3CC1C6B3.6060306@telepath.com>
 <3CC21747.5000501@telepath.com> <V+UgdHreGTJg@eisner.encompasserve.org>
 <x7vr8l871it.fsf@smaug.pushface.org> <4519e058.0204220534.2eb33730@posting.go
Mime-Version: 1.0
Date: Mon, 22 Apr 2002 22:31:16 GMT
X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit  (WinNT; U)
Xref: archiver1.google.com comp.lang.ada:22936
Date: 2002-04-22T22:31:16+00:00
List-Id: <comp.lang.ada>

Darren New wrote:
> 
> I.e., what keeps a bounded map from being implemented as a tree instead
> of a hash [table]? Indeed, for many types, I'd think a tree would be a better
> implementation, as a hashtable requires you to be able to manipulate the
> key items in a non-opaque manner, while a tree requires only a ordering
> operator.

Trees also have the advantage that they do not waste space.

The trouble with a tree is that, if it is not balanced, operations can
be O(N) in the worst case. If the tree is balanced, searching is O(log
N), but insertion and deletion are slow, because the tree must be
rebalanced after every modification.

This is why I use skip lists. They do not waste space, and operations
are O(log N) but no rebalancing is needed after modification.

-- 
Jeffrey Carter