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!news4.google.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!elnk-atl-nf1!newsfeed.earthlink.net!stamper.news.atl.earthlink.net!newsread1.news.atl.earthlink.net.POSTED!14bb18d8!not-for-mail Sender: Matthew Heaney@MHEANEYIBMT43 Newsgroups: comp.lang.ada Subject: Re: hashed_maps References: <1129046337.130908.137510@g47g2000cwa.googlegroups.com> <1129136684.840004.135310@g47g2000cwa.googlegroups.com> <1129214713.115873.151280@o13g2000cwo.googlegroups.com> <1129215331.736043.8600@g44g2000cwa.googlegroups.com> <1129217108.662259.56960@o13g2000cwo.googlegroups.com> From: Matthew Heaney Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 14 Oct 2005 04:35:49 GMT NNTP-Posting-Host: 24.149.57.125 X-Complaints-To: abuse@earthlink.net X-Trace: newsread1.news.atl.earthlink.net 1129264549 24.149.57.125 (Thu, 13 Oct 2005 21:35:49 PDT) NNTP-Posting-Date: Thu, 13 Oct 2005 21:35:49 PDT Organization: EarthLink Inc. -- http://www.EarthLink.net Xref: g2news1.google.com comp.lang.ada:5627 Date: 2005-10-14T04:35:49+00:00 List-Id: Simon Wright writes: > 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. Yes, that is correct. The associative containers must do better than O(n). If it were otherwise, they wouldn't provide any benefit (you could just use the sequence containers). The ordered containers (in GCC 4, and in the ref. impl. at tigris) are implemented using a red-black tree, and hence provide O(log n) time complexity even in the worst case. The hashed containers are implemented using a hash table, and therefore have O(1) time complexity on average. But note that hashed container complexity behavior is very sensitive to quality of hash function. In the problem here, you can convert an address to an integer, and use that as its hash value, so your hash function is perfect.