Re: BinaryPredicate Question

From:

"Daniel T." <daniel_t@earthlink.net>

Newsgroups:

comp.lang.c++.moderated

Date:

Wed, 31 Jan 2007 01:22:54 CST

Message-ID:

<daniel_t-0ACBB0.12090730012007@news.west.earthlink.net>

"James Kanze" <james.kanze@gmail.com> wrote:

Daniel T. wrote:

Otis Bricker <obricker@my-dejanews.com> wrote:

But I am a bit surprised that some have said that the version
operator()(const DataItem&,long) is the one that is needed, though I
might have misunderstood the comments. The couple of compilers I had
tried all worked with the operator()(long,const DataItem&). I tried
something else and found that for lower_bound my current compiler does
seem to want (const DI&,long). I can understand this.

If the test was simply std::less<DataItem>, I would have expected the
upper_bound to be calling less::operator()(myvalue,testValue) and the
first point that passed( or the end of range) would be the result. With
lower_bound and less, I would expect it to be testing
not(less::operator()(testValue,myValue)) and terminating the same way.

Of course, I imagine that it could be implemented in other ways. Or I
could just have my head on backwards today.

Your logic is correct. Upper and lower range functions need to be able
to work with forward interators so they must start at the beginning of
the range and progress from there. There really is no reason to have a
op() for going the other way in the container.

The specification says that they may make at most log n
comparisons, which isn't possible if they simply progress
linearly through the container.

Progressing linearly through the container would be ridiculous in any
case. We are talking about a container that is known to be sorted.

The key point here is that the algorithm doesn't need to know if two
elements are equal, so it doesn't need to be able to reverse the
arguments of the predicates operator.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]