[cfe-dev] Asymmetric lower_bound

[Ahmed Charles]

Jakob Stoklund Olesen wrote:
> On Aug 16, 2010, at 2:40 PM, Howard Hinnant wrote:
> >
> > The LWG has consistently affirmed over the years that lower_bound and upper_bound tolerate asymmetric compares (but in opposite senses).
> >
> >  lower_bound only requires:
> >
> >     *j < value or comp(*j, value)
> >
> >  upper_bound only requires:
> >
> >     (value < *j) or comp(value, *j)
> >
> > -Howard
>
> Thanks,
>
> I guess we will have to keep the other operator< around for MSVC's sake.
>
> /jakob

Note: saying which version of VC is helpful, but in this case it's the
debug checks in versions 8/9 (2005/2008). Quoting Stephan T. Lavavej,
who maintains Microsoft's STL implementation:

C++98/03 said:

25.3.3: "All of the algorithms in this section are versions of binary
search and assume that the sequence being searched is in order
according to the implied or explicit comparison function."

25.3.3.1/1: "Requires: Type T is LessThanComparable (20.1.2)."

The problem, of course, was that C++98/03 wasn't thinking about this
clearly, but it's obvious that whatever it was thinking, it was
thinking about homogeneous comparisons only.

The FCD, happily, speaks with crystal clarity:

25.4.3: "All of the algorithms in this section are versions of binary
search and assume that the sequence being searched is partitioned with
respect to an expression formed by binding the search key to an
argument of the implied or explicit comparison function."

25.4.3.1: "Requires: The elements e of [first,last) shall be
partitioned with respect to the expression e < value or comp(e,
value)."

I maintain that VC8/9's debug checks were perfectly acceptable
according to C++98/03. In any event, VC10 follows C++0x and permits
heterogeneous comparisons. I've got a todo to investigate re-enabling
the debug checks in a form friendly to heterogeneous comparisons. By
the way, providing additional comparators is the correct workaround
for VC8/9. Disabling HID (_HAS_ITERATOR_DEBUGGING) is wrong.