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-Thread: 103376,a8c6c308ebb6a246
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news1.google.com!news4.google.com!news.glorb.com!newsgate.cistron.nl!news.nl.colt.net!colt.net!nntp.theplanet.net!inewsm1.nntp.theplanet.net!newsfeed.icl.net!newsfeed.fjserv.net!peer-uk.news.demon.net!kibo.news.demon.net!news.demon.co.uk!demon!not-for-mail
From: Simon Wright <simon@pushface.org>
Newsgroups: comp.lang.ada
Subject: Re: hashed_maps
Date: Thu, 13 Oct 2005 20:47:16 +0100
Organization: Pushface
Message-ID: <m2hdblci7v.fsf@grendel.local>
References: <1129046337.130908.137510@g47g2000cwa.googlegroups.com>
 <wSS2f.9405$zQ3.3272@newsread1.news.pas.earthlink.net>
 <1129136684.840004.135310@g47g2000cwa.googlegroups.com>
 <uek6q6lo2.fsf@earthlink.net>
 <1129214713.115873.151280@o13g2000cwo.googlegroups.com>
 <1129215331.736043.8600@g44g2000cwa.googlegroups.com>
 <1129217108.662259.56960@o13g2000cwo.googlegroups.com>
NNTP-Posting-Host: pogner.demon.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: news.demon.co.uk 1129232834 23005 62.49.19.209 (13 Oct 2005 19:47:14
 GMT)
X-Complaints-To: abuse@demon.net
NNTP-Posting-Date: Thu, 13 Oct 2005 19:47:14 +0000 (UTC)
Cancel-Lock: sha1:szG6GekYUA9XRUZa8OyLhRvoGRs=
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (darwin)
Xref: g2news1.google.com comp.lang.ada:5608
Date: 2005-10-13T20:47:16+01:00
List-Id: <comp.lang.ada>

"Lucretia" <lucretia9@lycos.co.uk> writes:

> Now, I just need to know that what I'm doing with the ordered map
> isn't going to generate a linked list in which the search will end
> up linear as new C++ types are allocated as the key will be the
> address of the C++ instance. Should a hashed map be used, if so, how
> do you do this?  I've only seen examples of hashing with strings.

Matt will confirm, but I'm pretty sure that the ordered map uses a
red-black tree as its implementation. This would give you O(log n)
access time.