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,f2690a5e963b61b6
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news3.google.com!newshub.sdsu.edu!elnk-nf2-pas!newsfeed.earthlink.net!stamper.news.pas.earthlink.net!stamper.news.atl.earthlink.net!newsread3.news.atl.earthlink.net.POSTED!14bb18d8!not-for-mail
Sender: mheaney@MHEANEYX200
Newsgroups: comp.lang.ada
Subject: Re: GCC 4.0 Ada.Containers Cursor danger.
References: <1120474891.635131.216700@g44g2000cwa.googlegroups.com>
 <42cb8d21$0$22761$9b4e6d93@newsread2.arcor-online.net>
 <ldco4pwrxop4$.1py0a7isiagea.dlg@40tude.net>
 <z--dnRI60_7j_lHfRVn-qw@megapath.net>
 <tyi72ga8ch55$.3tea03tbwrtx.dlg@40tude.net>
 <42cd064c$0$10817$9b4e6d93@newsread4.arcor-online.net>
 <k62rlp2n1ls3.1cnwufmnuit7v.dlg@40tude.net>
 <42cda8c4$0$22780$9b4e6d93@newsread2.arcor-online.net>
 <1u3hh2597i4ne$.1ryetugksbmus.dlg@40tude.net> <uslyp8mmb.fsf@earthlink.net>
 <ad6fbg9gg773$.fzh0v45r7n53.dlg@40tude.net>
 <1120834341.499757.133770@g43g2000cwa.googlegroups.com>
 <1121093867.964444.232420@g14g2000cwa.googlegroups.com>
 <42d2bc2d$0$20148$9b4e6d93@newsread2.arcor-online.net>
 <1121134291.379399.79460@z14g2000cwz.googlegroups.com>
 <42d46b51$0$18005$9b4e6d93@newsread4.arcor-online.net>
 <rBlBe.100$Lv6.23@fe04.lga>
 <42d6ef47$0$7644$9b4e6d93@newsread2.arcor-online.net>
 <1eg30i81gqy2a$.ljhncmxt8d7w.dlg@40tude.net> <uu0iw8e2p.fsf@earthlink.net>
 <IM_Ce.6925$wN3.1659@fe07.lga>
From: Matthew Heaney <matthewjheaney@earthlink.net>
Message-ID: <ull436nbj.fsf@earthlink.net>
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Tue, 19 Jul 2005 11:35:12 GMT
NNTP-Posting-Host: 24.149.57.125
X-Complaints-To: abuse@earthlink.net
X-Trace: newsread3.news.atl.earthlink.net 1121772912 24.149.57.125 (Tue,
 19 Jul 2005 04:35:12 PDT)
NNTP-Posting-Date: Tue, 19 Jul 2005 04:35:12 PDT
Organization: EarthLink Inc. -- http://www.EarthLink.net
Xref: g2news1.google.com comp.lang.ada:3671
Date: 2005-07-19T11:35:12+00:00
List-Id: <comp.lang.ada>

Mikhail Terekhov <terekhov@emc.com> writes:

> >>[and again, sets could be searchable and not]
> > The sets in the Ada 2005 standard container library are searchable.
> 
> Then it is not the common set abstraction. In the common set
> abstraction search degenerates into membership test and the common set
> abstraction contains no such things like First, Last and Cursor.

All of the containers in the standard container library have a
membership test called Contains:

  function Contains (Container : Map; Key : Key_Type) 
    return Boolean;

   function Contains (Container : Set; Item : Element_Type) 
    return Boolean;

George's generic algorithm Generic_Find does a membership test too.  The
difference is that Contains is a primitive operation of the type, and
therefore takes advantage of the container's representation: for ordered
sets and maps, Contains executes in O(log n) time, and for the hashed
containers it executes in O(1) time.

Generic_Find performs a linear search, and hence executes in O(n) time.

The other, more subtle difference is that Contains tests for
"equivalence," and Generic_Find tests for "equality."  See my tutorial
notes online at charles.tigris.org if you don't understand equivalence.