Issue inside upper_bound

Issue inside upper_bound

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


Hi,
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
ordering
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 25.3.3.2 upper_bound, the Comp functor will only
needs to do _Pred(_Left, _Right). It doesn't need _Pred(_Right,
_Left).
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?
Thanks.
 
 
 

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.

http://www.yqcomputer.com/
http://www.yqcomputer.com/

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
inconsistent).

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
library.

I hope this helps,

Chris

 
 
 

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
mode.
2. Although there's a statement in http://www.yqcomputer.com/
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 25.3.3.2, 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:

http://www.yqcomputer.com/ #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.

Chris
 
 
 

Issue inside upper_bound

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


Hi Chris and Igore,

Thanks for your kindly help.