Ed Brey wrote:

> if (s.key_compare(k, *it))

Should be

    if (s.key_comp()(k, *it))

of course.

--

Valentin Bonnard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

ark@research.att.com (Andrew Koenig) wrote:


: In article <ZhG03.410$K6.21689@newscene.newscene.com>,
: John Potter <jpotter@falcon.lhup.edu> wrote:

: > From the HP/STL documentation dated 31 October 1995, Table 12
: > Associative container requirements (in addition to container):

: >   a.find(k)  returns an iterator pointing to an element with the key
: >   equal to k, or a.end() if such an element is not found.

: > I don't think the committee gets any blame here.  Yes, the code is the
: > same as lower_bound plus a test.  Yes, the VC documentation is talking
: > about the implementation details.  Yes, the standard allows other
: > inplementations which find other than the first match.  Yes, it
: > is likely that no implementation will bother to code it otherwise.

: Why not?  In general, finding an arbitrary matching element is faster
: than finding the first matching element.  Consider, for example,
: a sequence with a million identical elements.  If you stop as
: soon as you find a match, you save approximately 20 probes compared
: with finding the first matching element.

Yes, and with a million distinct elements the average goes up from 21
to about 22 with a max of 40.  I was thinking that the average was
higher.  Someone just might do it.  The cynic in me says that no one
will bother.  Anyway, I'm satisfied with the standard allowing it.

John



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

sbnaran@localhost.localdomain (Siemel Naran) wrote:


: On 10 May 99 14:34:32 GMT, Andrew Koenig <ark@research.att.com> wrote:

: >If you want to know whether an element with a given value exists
: >but don't care where it is, use binary_search.

: But binary_search is not part of the minimal interface.  It can be
: implemented trivially with
:    namespace myspace {
:       bool exists(...) { return std::lower_bound(...)==end; }
:    }

Sorry, lower_bound always returns something other than last except
when the target is greater than all elements.

   iterator it(lower_bound(fisrt, last, target));
   return it != last && ! (target < *it);

: So why the they put this function in the STL?

So that it would be done correctly?  ;-)

John



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jerry Coffin <jcoffin@taeus.com> wrote in message
news:MPG.11a628cbb6c36baa989abb@news.mindspring.com...
[ ... ]
> > Thanks for pointing that out.  I was going off of the VC6 documentation
for
> > multiset::find, which says it returns the earliest element.  I should
have
> > known better than to trust VC's STL.  This could be one of VC's nastiest
> > bugs yet.
>
> What complete and utter nonsense.  It's not a bug or anything close.
> Its documentation tells you how it works, and it works in accordance
> with the standard -- that's clearly NOT a bug.
[ ... ]
> If somebody takes the documentation of one particular implementation
> (ANY part of an implementation) as meaning much about what other
> implementations do, he deserves exactly what he gets.

Your interpretation of VC's standard library documentation is very different
from mine.  I'm surprised that when you see the title page of "Standard C++
Library Reference", you consider it to be specific to VC's implementation
only.  This would make the reference, which is well-indexed and convenient,
unusable for writing portable code.  Fortunately, it is clear that the
intent is to provide a reference to the standard C++ library, and mention
implementation details where necessary.  For evidence, consider the numerous
occasions were you find: "In this implementation, if a translator does not
support member template functions...".  This documentation is not specific
to the VC compiler, and it is not much of a stretch to conclude that the
documentation only describes library implmentation details where necessary
to work around compiler shortcomings.

The real problem is that Microsoft didn't put the following statement on the
box and in MSDN:
"Even though we're shipping this product after C++ has been standardized,
we're including a buggy, three-year-old draft standard C++ library
implementation and its documentation, since we don't use it anyway."

Since VC attempts to document the standard C++ library, and does it wrong,
it has a bug.  Moreover, there are several standard C++ library
documentation errors.  VC users must trade off the convenience versus the
lack of correctness.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 10 May 99 14:34:32 GMT, Andrew Koenig <ark@research.att.com> wrote:

>If you want to know whether an element with a given value exists
>but don't care where it is, use binary_search.

But binary_search is not part of the minimal interface.  It can be
implemented trivially with
   namespace myspace {
      bool exists(...) { return std::lower_bound(...)==end; }
   }
So why the they put this function in the STL?

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <ZhG03.410$K6.21689@newscene.newscene.com>,
John Potter <jpotter@falcon.lhup.edu> wrote:

> From the HP/STL documentation dated 31 October 1995, Table 12
> Associative container requirements (in addition to container):

>   a.find(k)  returns an iterator pointing to an element with the key
>   equal to k, or a.end() if such an element is not found.

> I don't think the committee gets any blame here.  Yes, the code is the
> same as lower_bound plus a test.  Yes, the VC documentation is talking
> about the implementation details.  Yes, the standard allows other
> inplementations which find other than the first match.  Yes, it
> is likely that no implementation will bother to code it otherwise.

Why not?  In general, finding an arbitrary matching element is faster
than finding the first matching element.  Consider, for example,
a sequence with a million identical elements.  If you stop as
soon as you find a match, you save approximately 20 probes compared
with finding the first matching element.
--
    Andrew Koenig
    ark@research.att.com
    http://www.research.att.com/info/ark



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7hhn2c$667@interserv.etn.com>, brey@afd.mke.etn.com
says...

[ ... ]

> Thanks for pointing that out.  I was going off of the VC6 documentation for
> multiset::find, which says it returns the earliest element.  I should have
> known better than to trust VC's STL.  This could be one of VC's nastiest
> bugs yet.

What complete and utter nonsense.  It's not a bug or anything close.
Its documentation tells you how it works, and it works in accordance
with the standard -- that's clearly NOT a bug.

> How many programmer's naively believe the documentation and write
> classes that work today, only to find them eventually fail when recompiled
> with future STL implementations.

If somebody takes the documentation of one particular implementation
(ANY part of an implementation) as meaning much about what other
implementations do, he deserves exactly what he gets.

If you look at the documentation for ANY conforming implementation of
C++ (or anything that even attempts to come close to conforming)
you're going to find documentation on things you canNOT depend upon
other implementations doing -- just for example, documentation of the
implementation-defined aspects is absolutely required, and it's purely
accidental if another implementation happens to make the same
decisions.

The documentation for an implementation is specific to that
implementation.  If you assume it documents another implementation,
you're making an assumption that is not, never was, and never will be
valid.  This applies regardless of what compiler you use.

I agree that ideally an implementation will tell you which parts of
what it documents are portable and which parts are specific to that
implementation, but it's a LONG ways from being a bug if they don't.
Doing a bit of looking through a few other compilers I have around,
the majority do a poor job (at best) of documenting exactly what's
portable and what isn't.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"P.J. Plauger" <pjp@plauger.com> wrote:
: Ed Brey wrote in message <7hhn2c$667@interserv.etn.com>...
: >James Kuyper <kuyper@wizard.net> wrote in message
: >news:373B77B1.4C82E9A7@wizard.net...
: >>
: >> The final Standard says nothing about find() that is specific to
: >> multiset. The associative container requirements say only that it
: >> locates a key that compares equal, not that it points to the first one.
: >
: >Thanks for pointing that out.  I was going off of the VC6 documentation for
: >multiset::find, which says it returns the earliest element.  I should have
: >known better than to trust VC's STL.

: Oh, why? It happens to be correct, in that it describes the actual behavior
: of the original STL (from which most existing implementations are derived)
: and the STL shipped with VC++. The C++ Standard got reworked by several
: hands over several years, not always with sufficient checking. Looks like
: the final spec ended up weaker than the original intent.

>From the HP/STL documentation dated 31 October 1995, Table 12
Associative container requirements (in addition to container):

  a.find(k)  returns an iterator pointing to an element with the key
  equal to k, or a.end() if such an element is not found.

I don't think the committee gets any blame here.  Yes, the code is the
same as lower_bound plus a test.  Yes, the VC documentation is talking
about the implementation details.  Yes, the standard allows other
inplementations which find other than the first match.  Yes, it
is likely that no implementation will bother to code it otherwise.  Yes,
portable code can not depend on finding first.  Have I been positive
enough here?

Since multi_map does not support operator[], maybe it should also not
support find?

John
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Ed Brey" <brey@afd.mke.etn.com> wrote:

: P.J. Plauger <pjp@plauger.com> wrote in message
: news:7hjvdt$r49$1@news.harvard.net...
: > Ed Brey wrote in message <7hhn2c$667@interserv.etn.com>...
: > >James Kuyper <kuyper@wizard.net> wrote in message
: > >news:373B77B1.4C82E9A7@wizard.net...
: > >>
: > >> The final Standard says nothing about find() that is specific to
: > >> multiset. The associative container requirements say only that it
: > >> locates a key that compares equal, not that it points to the first one.
: > >
: > >Thanks for pointing that out.  I was going off of the VC6 documentation
: for
: > >multiset::find, which says it returns the earliest element.  I should
: have
: > >known better than to trust VC's STL.
: >
: > Oh, why? It happens to be correct, in that it describes the actual
: behavior
: > of the original STL (from which most existing implementations are derived)
: > and the STL shipped with VC++. The C++ Standard got reworked by several
: > hands over several years, not always with sufficient checking. Looks like
: > the final spec ended up weaker than the original intent.

How about some code?  Here is my implementation's code.

  link_type y = header;        // Last node which is not less than k.
  link_type x = root();        // Current node.

  while (x != 0)
    if (!key_compare(key(x), k))
      y = x, x = left(x);
    else
      x = right(x);

  iterator j = iterator(y);
  return (j == end() || key_compare(k, key(j.node))) ? end() : j;

That's a nice copy of lower_bound but how about:

  while (x != 0)
    if (key_compare(k, key(x))
      x = left(x);
    else if (key_compare(key(x), k))
      x = right(x);
    else {
      y = x;
      x = 0;
      }
  iterator j = iterator(y);
  return j;

That could be considered more efficient by some.  It's not.

Or how about an absurd version:

  while (x != 0)
    if (key_compare(k, key(x))
      x = left(x);
    else if (key_compare(key(x), k)
      x = right(x);
    else {
      y = x;
      switch (rand() % 3) {
        case 0 :
          x = 0;
          break;
        case 1 :
          x = left(x);
          break;
        case 2 :
          x = right(x);
          break;
        }
      }
  iterator j = iterator(y);
  return j;

With this last version, assert(a.find(k) == a.find(k)) could fail!

I like this flexability :)

Just dont use multimap::find(k);

That could also answer the Subject: question.  At least it is
meaningful!

John



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter <jpotter@falcon.lhup.edu> wrote in message
news:ZhG03.410$K6.21689@newscene.newscene.com...
>
>   a.find(k)  returns an iterator pointing to an element with the key
>   equal to k, or a.end() if such an element is not found.
>
> I don't think the committee gets any blame here.  Yes, the code is the
> same as lower_bound plus a test.

I think the committee should consider the efficiency tradeoffs between the
two approaches.  The current definition that a.find(k) can return any
element with key equal to k has the following advantages and disadvantages,
depending on the use case:

Use case 1: The user wants to find any matching element.  The current
definition provides the advantage that potentially an implementation can be
more efficient than if it had to return the earliest element.

Use case 2: The user wants to find the first matching element.  The user
does this:
S::iterator it = s.lower_bound(k);
if (s.key_compare(k, *it))
    it = s.end();

I'd have to do a little head scratching to make sure I've done the
predicating correctly above, which is one problem with this approach.  A
more severe problem is that the predicate object needs to be copied, which
is too expensive for some applications.

Use case 3: The user wants to find the first matching element.  The user
does this:
std::pair<S::iterator it, S::iterator it> itit = s.equal_range(k);
S::iterator it = itit.first != itit.second ? s.end() : itit;

The question in my mind is whether the performance boost in use case 1
outweighs the performance loss in use case 3, (loss relative to performance
achievable if use case 3 could use a find member that returned the earliest
element).  If no implementation ever returns an element that is other than
the earliest, there is no gain, and only a loss.

Can any library implementers and/or visionaries comment on whether an
implementation will ever take advantage of the latitude of the current
definition of a.find(k)?  If the answer is no, I would submit that the
definition be tightened to improve the performance for users who want the
first matching element.




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

P.J. Plauger <pjp@plauger.com> wrote in message
news:7hjvdt$r49$1@news.harvard.net...
>
> Ed Brey wrote in message <7hhn2c$667@interserv.etn.com>...
> >James Kuyper <kuyper@wizard.net> wrote in message
> >news:373B77B1.4C82E9A7@wizard.net...
> >>
> >> The final Standard says nothing about find() that is specific to
> >> multiset. The associative container requirements say only that it
> >> locates a key that compares equal, not that it points to the first one.
> >
> >Thanks for pointing that out.  I was going off of the VC6 documentation
for
> >multiset::find, which says it returns the earliest element.  I should
have
> >known better than to trust VC's STL.
>
> Oh, why? It happens to be correct, in that it describes the actual
behavior
> of the original STL (from which most existing implementations are derived)
> and the STL shipped with VC++. The C++ Standard got reworked by several
> hands over several years, not always with sufficient checking. Looks like
> the final spec ended up weaker than the original intent.

Do you think this is an oversight in the C++ standard that should be flags
as an error and corrected?  Or did the intent change?  Either way, it is
important that programmers have clear direction on how to use find.  If the
C++ standard is correct, then programmers must be careful not to assume they
will get the earliest element, or they risk having to search for elusive,
not-necessarily repeatible bugs in the future.  On the other hand, STL
implementors may all agree that there is just too much code out there that
assumes find returns the earliest element and it's inexpensive to do so
anyway, in which case the official standard should be changed to allow
programmers to know they can safely take advantage of the de facto standard.

> >This could be one of VC's nastiest
> >bugs yet.  How many programmer's naively believe the documentation and
write
> >classes that work today, only to find them eventually fail when
recompiled
> >with future STL implementations.
>
> Perhaps a few, given that WG21 issued about a dozen drafts of the C++
> Standard from the time STL was added.

As far as VC is concerned, I lump Microsoft's handling of the documentation
bug in with their handling of the other bugs in their STL.  The problems
stem from the fact that they are using a very old implementation (and
associated documentation), despite the fact that VC6 shipped after the C++
standard was ratified.  Their failure to issue bug reports and workarounds
to their problems differs from what I would expect a reputable compiler
vendor to do.

I appreciate the work that Dinkumware has done in backfilling for
Microsoft's lack of support.  Perhaps this (and some more minor)
documentation fixes should be listed on the "VC fixes" page.  I realize it
is probably not possible to seamlessly "override" documentation in MSDN.
Still, errata notes are far better than nothing.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Andrew Koenig wrote:

> If you want to know whether an element with a given value exists
> but don't care where it is, use binary_search.
>
If binary_search would return an iterator instead a bool we would know
both,
that the element exists and its position.

--
Ryszard Kabatek
Martin-Luther University Halle-Wittenberg, Department of Physical
Chemistry
Geusaer Str. 88, 06217 Merseburg, Germany
Tel. +49 3461 46 2487 (2466) Fax. +49 3461 46 2129


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ryszard Kabatek <rysio@rumcajs.chemie.uni-halle.de> wrote:

: Andrew Koenig wrote:

: > If you want to know whether an element with a given value exists
: > but don't care where it is, use binary_search.
: >
: If binary_search would return an iterator instead a bool we would know
: both, that the element exists and its position.

What iterator does it return when it is not there?
When there are multiple copies, which one does it find?

The library has four very useful functions.  Let's not try to
break it with a partial solution to some unknown problem.

John
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter <jpotter@falcon.lhup.edu> wrote in message
news:o8i_2.39193$cr6.1752793@newscene.newscene.com...
>
> : If binary_search would return an iterator instead a bool we would know
> : both, that the element exists and its position.
>
> What iterator does it return when it is not there?
> When there are multiple copies, which one does it find?
>
> The library has four very useful functions.  Let's not try to
> break it with a partial solution to some unknown problem.

There are good answers to your questions: the find function in
(multi)map/set already provides them.

I've always found it odd that STL breaks down its parallelism between an
ordered vector and an ordered set with the binary search function.

Consider how you would perform the following methods on an ordered vector
versus multiset:

method                  multiset member fn      fn used with vector
------------------      ------------------      -------------------
find lower bound        lower_bound             lower_bound
find upper bound        upper_bound             upper_bound
find first, if any      find                    binary_search

In all cases, I am referring to methods that perform the find in O(log)
time.  In the case of a multiset, if there are multiple matching elements,
find returns an iterator to the first one.  If there are no matches, find
returns end.

There is no reason why binary_search should not follow the same protocol.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Ed Brey" <brey@afd.mke.etn.com> wrote:

: John Potter <jpotter@falcon.lhup.edu> wrote in message
: news:o8i_2.39193$cr6.1752793@newscene.newscene.com...
: >
: > : If binary_search would return an iterator instead a bool we would know
: > : both, that the element exists and its position.
: >
: > What iterator does it return when it is not there?
: > When there are multiple copies, which one does it find?

: There are good answers to your questions: the find function in
: (multi)map/set already provides them.

: I've always found it odd that STL breaks down its parallelism between an
: ordered vector and an ordered set with the binary search function.

: Consider how you would perform the following methods on an ordered vector
: versus multiset:

: method                  multiset member fn      fn used with vector
: ------------------      ------------------      -------------------
: find lower bound        lower_bound             lower_bound
: find upper bound        upper_bound             upper_bound
: find first, if any      find                    binary_search

Not quite on the last one:

  find one or end         find                    none
  contains?               count                   binary_search

: In all cases, I am referring to methods that perform the find in O(log)
: time.  In the case of a multiset, if there are multiple matching elements,
: find returns an iterator to the first one.  If there are no matches, find
: returns end.

Are you sure about "first"?  I don't have my IS here, but CD2 only
specifies that it will find a match or end.  I think that finding
the root of the subtree which contains the matches would be correct.
A binary_search which returned an iterator should also be allowed to
return any match or end.  I would not like that and accept the bool.

: There is no reason why binary_search should not follow the same protocol.

Nor any reason why it should.  The reason that it doesn't is that it
doesn't :)

Binary_search is a general algorithm.  The associative containers have
special versions because the general algorithms do not perform well
and the performance is possible with the specializations.

I could accept the arguement that multimap has misnamed functions which
do not agree with the general functions, but not that the general
functions should match the special ones.

I maintain that _contains_ is a useful function which is spelled
binary_search for the general algorithm and count for the associative
containers.  It answers a useful question.

  if (binary_search(v.begin(), v.end(), k))

becomes

  if (binary_search(v.begin(), v.end(), k) != v.end())

No big deal, but what are the great advantages to changing it?

  if ((it = lower_bound(v.begin(), v.end(), k)) != v.end() &&
  k == *it)

becomes

  if ((it = binary_search(v.begin(), v.end(), k)) != v.end())

Sorry, I just don't see any compelling reason to change things.
IMHO, the standard provides a useful minimal library.  As is
often stated in this forum, the library is a starting point and
it can easily be extended.

template <typename I, typename T>
I binary_find_first_or_end (I first, I last, T const& target) {
   I it = lower_bound(first, last, target);
   return it == last || target < *it ? last : it;
   }

I prefer to use lower_bound directly and make only the tests which
interest me.  It's nice that binary_search is provided for the
times when I am interested in the tests that it makes, but I could
do without it entirely.

John
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter wrote:
....
> : In all cases, I am referring to methods that perform the find in O(log)
> : time.  In the case of a multiset, if there are multiple matching elements,
> : find returns an iterator to the first one.  If there are no matches, find
> : returns end.
>
> Are you sure about "first"?  I don't have my IS here, but CD2 only
> specifies that it will find a match or end.  I think that finding

The final Standard says nothing about find() that is specific to
multiset. The associative container requirements say only that it
locates a key that compares equal, not that it points to the first one.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote in message
news:373B77B1.4C82E9A7@wizard.net...
>
> The final Standard says nothing about find() that is specific to
> multiset. The associative container requirements say only that it
> locates a key that compares equal, not that it points to the first one.

Thanks for pointing that out.  I was going off of the VC6 documentation for
multiset::find, which says it returns the earliest element.  I should have
known better than to trust VC's STL.  This could be one of VC's nastiest
bugs yet.  How many programmer's naively believe the documentation and write
classes that work today, only to find them eventually fail when recompiled
with future STL implementations.

I agree that only the associative containers should have member functions
for doing lookup, since only they need them for efficiency.  However, I
consider it poor interface design for the member and non-member lookup
functions to not parallel other where possible.

STL's parallelism is fine for unordered vectors, since then std::find and
std::multiset::find give equivilent results, except for efficiency, which
cannot be made equivilent.

For ordered vectors, it is understandable for there to not be complete
parallelism, since the name std::find is already in use and doesn't make
obvious that the vector must be ordered.  std::binary_search is a good name
for the optimized version of std::find, and it is fine to think of it as the
optimized parallel to std::multiset::find.  If std::binary_search answered
the same question as std::multiset::find, "Where is it?", instead of "Is it
there?", it would be a parallel to the fullest extent possible.
Unfortunately, it doesn't and I think that this is a deficiency in the
interface design.

In order to maintain a minimal interface, I don't think that a "Is it
there?" method should be included unless it could be implemented much more
efficiently than "Where is it"?  As far as I know, this isn't the case.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>For ordered vectors, it is understandable for there to not be complete
>parallelism, since the name std::find is already in use and doesn't make
>obvious that the vector must be ordered.  std::binary_search is a good name
>for the optimized version of std::find, and it is fine to think of it as the
>optimized parallel to std::multiset::find.  If std::binary_search answered
>the same question as std::multiset::find, "Where is it?", instead of "Is it
>there?", it would be a parallel to the fullest extent possible.
>Unfortunately, it doesn't and I think that this is a deficiency in the
>interface design.
>
>In order to maintain a minimal interface, I don't think that a "Is it
>there?" method should be included unless it could be implemented much more
>efficiently than "Where is it"?  As far as I know, this isn't the case.

In fact, binary_search is implemented in terms of lower_bound in both
the SGI and visual C++ implementations.  The only thing these
versions do extra is perform the comparison you have to do manually
with lower bound.

I don't like the fact that binary_search throws information away.
Of course, it's trivial to write a function that retains the info:

template<class FwdIt, class StrictWeakComp>
FwdIt binary_find(FwdIt first, FwdIt last, StrictWeakComp& val)
{
    FwdIt it = std::lower_bound(first, last, val);
    return it == last || val < *it ? last : it;
}

This returns an iterator to the lowest match or last if none is
found.  A version taking a comparison fn. object is equally
simple.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ed Brey wrote in message <7hhn2c$667@interserv.etn.com>...
>James Kuyper <kuyper@wizard.net> wrote in message
>news:373B77B1.4C82E9A7@wizard.net...
>>
>> The final Standard says nothing about find() that is specific to
>> multiset. The associative container requirements say only that it
>> locates a key that compares equal, not that it points to the first one.
>
>Thanks for pointing that out.  I was going off of the VC6 documentation for
>multiset::find, which says it returns the earliest element.  I should have
>known better than to trust VC's STL.

Oh, why? It happens to be correct, in that it describes the actual behavior
of the original STL (from which most existing implementations are derived)
and the STL shipped with VC++. The C++ Standard got reworked by several
hands over several years, not always with sufficient checking. Looks like
the final spec ended up weaker than the original intent.

>                                                              This could be
one of VC's nastiest
>bugs yet.  How many programmer's naively believe the documentation and write
>classes that work today, only to find them eventually fail when recompiled
>with future STL implementations.

Perhaps a few, given that WG21 issued about a dozen drafts of the C++
Standard from the time STL was added.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>I am wondering why binary_search returns a bool instead of an
>iterator type.  Wouldn't the function be more useful returning
>an iterator?  It seems I have to use find_if to get at the
>item.  Please explain!
>
>Eric

The STL provides four binary search algorithms: binary_search,
lower_bound, upper_bound, and equal_range.  Use one of
the latter three to obtain iterator(s) to matching element(s).

This arrangement is necessary, because a range can contain
more than one matching element.

ashley


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7h2osm$i78@news.or.intel.com> , "Eric" <eguad@usa.net> wrote:

>
> I am wondering why binary_search returns a bool instead of an
> iterator type.  Wouldn't the function be more useful returning
> an iterator?  It seems I have to use find_if to get at the
> item.  Please explain!

I think lower_bound is what you're looking for. If I remember correctly:

template <class It, class X>
It binary_find( It start, It finish, const X& x )
{
    It p = std::lower_bound( start, finish, x );
    return ( p != finish && *p == x ) ? p : finish;
}

On why it was designed this way I'm not qualified to comment.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Eric" <eguad@usa.net> wrote:

: I am wondering why binary_search returns a bool instead of an
: iterator type.  Wouldn't the function be more useful returning
: an iterator?  It seems I have to use find_if to get at the
: item.  Please explain!

There is a family of functions each of which is useful.  Binary_search
answers the question, "Is it there?"  It sounds like you are looking for
lower_bound which returns an iterator to the first item greater than or
equal to the target, the first place to insert the target and keep the
list ordered.  It answers the question, "Where is it or should it be?"
There is also upper_bound which returns an iterator to the first item
greater than the target, the last place to insert the target and keep
the list ordered.  It answers the question, "Where should it be
inserted?"  Equal_range returns a pair of iterators giving lower_bound
and upper_bound.  It answers the question, "Where are they?"

I agree that binary_search does not appear to be that useful taken in
isolation; however, the family answers all the questions.

John



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

[This followup was also e-mailed to the cited author for speed -- please
follow up in the newsgroup.]

Dixitque eguad@usa.net (Eric) in comp.std.c++:
>
>I am wondering why binary_search returns a bool instead of an
>iterator type.  Wouldn't the function be more useful returning
>an iterator?

I believe binary_search() is meant to be an existence test. When you
actually want to find the element, there's lower_bound() and its
siblings.

--
There's no need to e-mail me a copy of a follow-up; but if you do,
please identify it as such.

Stan Brown, Oak Road Systems, Cleveland, Ohio, USA
                                    http://www.mindspring.com/~brahms/
My reply address is correct as is. The courtesy of providing a correct
reply address is more important to me than time spent deleting spam.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 9 May 1999 13:06:57 GMT, Eric <eguad@usa.net> wrote:

>I am wondering why binary_search returns a bool instead of an
>iterator type.  Wouldn't the function be more useful returning
>an iterator?  It seems I have to use find_if to get at the
>item.  Please explain!

Agreed.  I don't know why they have std::binary_search at all.
Take a look at std::lower_bound and std::upper_bound.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I am wondering why binary_search returns a bool instead of an
iterator type.  Wouldn't the function be more useful returning
an iterator?  It seems I have to use find_if to get at the
item.  Please explain!

Eric




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]