Issue inside upper_bound

Issue inside upper_bound

Post by av » Fri, 22 Aug 2008 17:33:10

I'm using VS2005. Consider the following code:

int main()
class A{};
class B{};

struct Comp : public binary_function<A, B, bool>{
bool operator()(const A&, const B&) {return true;}
B *pB;
upper_bound(pB, pB, A(), Comp());
return 0;

The above codes only gets compile error in debug version. It works
fine in release version. According to the error message, the problem
is in the implementation of _Debug_lt_pred(). ( Please check xutility
line 319 ):

template<class _Pr, class _Ty1, class _Ty2> inline
bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, _Ty1& _Left,
_Ty2& _Right,
const wchar_t *_Where, unsigned int _Line)
{ // test if _Pred(_Left, _Right) and _Pred is strict weak
if (!_Pred(_Left, _Right))
return (false);
else if (_Pred(_Right, _Left))
_DEBUG_ERROR2("invalid operator<", _Where, _Line);
return (true);

The functor Comp fails in this statement: (_Pred(_Right, _Left).
According to C++ SPEC upper_bound, the Comp functor will only
needs to do _Pred(_Left, _Right). It doesn't need _Pred(_Right,
I think it's kind of bug that prevent the developer offering Comp with
different type of parameters. Is it possible to get fix in next patch?

Issue inside upper_bound

Post by Chris » Fri, 22 Aug 2008 19:21:20

On Thu, 21 Aug 2008 01:33:10 -0700 (PDT), av < XXXX@XXXXX.COM >

[ ... ]

Hi there,

When you apply std::upper_bound to a sequence, the predicate you
supply is used to define the order of that sequence. For this to work,
the arguments supplied to the predicate must be of the same type.

So, there are two problems with struct Comp:

1. If the sequence is of objects of type B, then Comp should be
declared as:

struct Comp : public std::binary_function<B, B, bool>

2. Comp's operator() always returns true, so it doesn't define a
correct ordering for the sequence (ie, for two values x and y, your
program will think that x > y and y > x, which is obviously

The reason it doesn't compile in a Debug build is because of the extra
checks that VC applies when compiling code that uses the standard

I hope this helps,



Issue inside upper_bound

Post by av » Sat, 23 Aug 2008 01:09:58

Hi Chris,
1. Comp's operator() always returns true is just to simplify the demo
code. My point is that VC's extra check make the code failed in debug
2. Although there's a statement in
mentioned that "Two objects x and y are equivalent if both f(x, y) and
f(y, x) are false.", I don't think that f(y, x) is a necessary
operation. According to ISO/IEC 14882:2003, only comp(value,
*j) operation is described.
BTW, the above not only compiles well in VC8 release mode, it also
works in g++.

Issue inside upper_bound

Post by Igor Tande » Sat, 23 Aug 2008 02:47:33

The extra checks are actually legal under the current standard.
Heterogeneous search of the kind you attempt is not well defined: the
standard requires the comparator to be a strict weak ordering, and the
definition of the latter talks about comparisons between objects of the
same type. Technically, your predicate is not a strict weak ordering,
and your code is invalid.

Most STL implementation will accept and work correctly for a
heterogeneous search, but your predicate should implement three
overloads of operator(): taking (B, B), (B, A) and (A, B).

Future version of the standard will likely clarify the situation, and
make your code good as written. For more details, see DR270: #270

With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Issue inside upper_bound

Post by Chris » Sat, 23 Aug 2008 03:52:53

On Thu, 21 Aug 2008 13:47:33 -0400, "Igor Tandetnik"

Thanks for your input, Igor. Very interesting.


Issue inside upper_bound

Post by av » Sat, 23 Aug 2008 11:53:24

Hi Chris and Igore,

Thanks for your kindly help.