[libc++] possible bug?

Hello *,

just tried to compile SYMPHONY-5.4.4 with clang 3.0 + libc++ (tag 31). While compiling it I receive this error:

include/c++/v1/algorithm:643:97: error: invalid operands to binary expression
(‘const reducedCost’ and ‘const reducedCost’)
_LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

/home/ovanes/toolsets/clang-3.0/include/c++/v1/algorithm:4433:13: note: in instantiation of member function 'std::__1::__less<reducedCost,
>::operator()' requested here
if (__comp(*__ptr, *--__last))
^
/home/ovanes/toolsets/clang-3.0/include/c++/v1/algorithm:4524:13: note: in instantiation of function template specialization
'std::__1::__push_heap_back<std::__1::__less<reducedCost, reducedCost> &, reducedCost *>' requested here
__push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
^
/home/ovanes/toolsets/clang-3.0/include/c++/v1/algorithm:4539:5: note: in instantiation of function template specialization
'std::__1::__make_heap<std::__1::__less<reducedCost, reducedCost> &, reducedCost *>' requested here
__make_heap<_Comp_ref>(__first, __last, __comp);
^
/home/ovanes/toolsets/clang-3.0/include/c++/v1/algorithm:4548:5: note: in instantiation of function template specialization
'std::__1::make_heap<reducedCost *, std::__1::__less<reducedCost, reducedCost> >' requested here
_VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
^
/home/ovanes/toolsets/clang-3.0/include/c++/v1/__config:174:15: note: expanded from:
#define _VSTD std::_LIBCPP_NAMESPACE

I stripped down a code example which reproduces the error. This is not my code, this the code from the lib (please don't judge me when looking to it ;)

struct reducedCost
{
/** To avoid computing two times the same row direction will have strange
values, direction is -1 or 1 if for only one of the two direction
rc is <0 and is -2 or 2 if the two direction have one <0 rc with the sign
indicating which one of the two directions is the best.<br>
Note that by theory only one reduced cost (for u_i, or v_i)
maybe negative for each direction.
*/
int direction;
/** gammSign is the sign of gamma (corresponding to taking rc for u_i or v_i)
for the best of the two rc for this row.*/
int gammaSign;
/** gammaSign2 is the sign of gamma for the worst of the two rc for this row.*/
int gammaSign2;
/** if both reduced costs are <0 value is the smallest of the two.*/
double value;
/** greatest of the two reduced costs */
double value2;
/** index of the row.*/
int row;
bool operator<(const reducedCost & other)
{
return (value>other.value);
}
};

int main()
{
reducedCost r[100]={};

std::make_heap(&r[0], &r[0]+100);
return 0;
};

I think the problem results because std::less is not defined directly in std namespace, but in std::__1 and was not properly introduced into the std-Namespace? Because specializing std::less<reduceCost> still produces the same error:

namespace std
{
template<>
struct less<reducedCost>
: ::std::binary_function<reducedCost, reducedCost, bool>
{
bool operator()(const reducedCost & lhs, const reducedCost & rhs)const
{
return lhs.value>rhs.value;
}
};
}

But, if explicitly specializing std::less<reducedCost> as comparison functor fixes the problem.

std::make_heap(&r[0], &r[0]+100, std::less<reducedCost>());

Thanks,
Ovanes

Hello *,
just tried to compile SYMPHONY-5.4.4 with clang 3.0 + libc++ (tag 31). While
compiling it I receive this error:

include/c++/v1/algorithm:643:97: error: invalid operands to binary
expression
('const reducedCost' and 'const reducedCost')
_LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1&
__y) const {return __x < __y;}

[...]

bool operator&lt;\(const reducedCost &amp; other\)

Missing const here. It is often preferable to avoid making operators member functions when you can avoid it.

Hello Marc,

you are definitely right. I overlooked it, since as already wrote this is not my code (just copy pasted it from the lib)… But in my tests I commented out this operator< and provided the specialization of std::less, to just test it and it failed as well. I did not test with both enable (operator< and less-specialization). Actually this code is somehow really bad, because less is actually not less but greater :wink: This code compiles fine with gcc and clang + gcc’s version of stdlib. As far as I remember the standard requires that std::less is specialized to allow the less comparison or the operator< is implicitly used through the generalized less. In my tests less specialization was not considered by make_heap. This is my point.

Thanks,
Ovanes

Two questions:

1. Does it work if you actually specify that `operator<` is `const` ?

2. Did you were careful about putting the specialization of `less` (for
this class) before its first use ? (it is not clear from your example)

If you could, for example, provide a simple attachment that reproduces the
issue it would be slightly simpler to investigate.

-- Matthieu

Sorry, don't know why this email went directly to Matthieu instead of the
list...

The make_heap function overload that does not take a comparator is specified to use operator<, not less<T>, in 25.4 [alg.sorting]/p1.

Howard

Howard,

many thanks for answer and sorry for noise. I falsly assumed, that
std::less specialization would be enough. I was looking for that paragraph
but not in make_heap specification and not in the superordinate paragraphs.
Thanks for pointing that out!

With Kind Regards,
Ovanes