Can you use std::less_equal with std::sort even though it isn't a strict weak ordering?

Question

From http://stdcxx.apache.org/doc/stdlibref/less-equal.html:

You can pass a less_equal object to any algorithm that requires a binary function. For example, the sort() algorithm can accept a binary function as an alternate comparison object to sort a sequence. less_equal would be used in that algorithm in the following manner:

vector<int> vec1;
sort(vec1.begin(), vec1.end(), less_equal<int>());

Now I am confused, is the documentation above correct ?

Vilayet

You can sort it however you want with the custom comparator. – Gouge

@Gouge Are you sure ? I think the result can be undefined if the comparator is not strict weak order – Vilayet

@chris: OP is right, the comparator must use strict ordering. The problem with non-strict ordering is that you can have both i1 <= i2 and i2 <= i1 which may block progress of the sort algorithm. – Uptotheminute

Sorry, I answered a different question than you were asking. – Gouge

It will probably still work with a usual implementation (in VC, it uses qsort, heap sort or insertion sort depending on list size). – Keitel

Did you try actually adding some equal values to the vector and then sorting it? Generally that's when an assert/exception would happen. You can pass anything you want as a comparator for an empty vector since it'll never be used. – Mortimer

@Keitel Heh! discovered this by getting singed on g++ by this, thought less_equals will lead to less data movement. – Vilayet

@RetiredNinja testing based development is ok, but knowing the correct behavior is better, after all, there only so many things that one can test. – Vilayet

@RetiredNinja: what makes you think you'd get an assertion or exception if it failed? – Scutt

@jalf Visual Studio will assert if the comparator is incorrect in debug mode. Presumably other compilers are free to do whatever they like to point out the error or nothing at all. – Mortimer

@RetiredNinja and how exactly will Visual Studio find out if the comparator is "incorrect", which in this context means violates strict weak orderedness ? – Vilayet

@Vilayet The rules for strict weak ordering are easy enough to validate. – Mortimer

@RetiredNinja please elaborate, am very curious. Say I have objects of class C. How does the compiler verify op(C,C) is valid. – Vilayet

I have one question. Why do std::sort need to compare both a < b and b < a ? standard sorting algorithms compare one way , not both way – Functionary

@Ranju: The algorithms compare whatever values it finds in the various positions in the sequence. Whether it checks a < b or b < a depends on where a and b are in the sequence. And since they may be relocated as the algorithm progresses, its possible that the same two values are compared again, only the other way around. – Erratic

Answer 1

You are right, std::sort requires the comparer to define a strict weak ordering.

Which means that std::less_equal should not be used with std::sort. It can still be used with a number of other standard algorithms though, which take a binary function and which do not have the strict weak ordering requirement.

Scutt

So is it so that stdcxx's sort is not standard compliant and still works with <= ? – Vilayet

Given that they claim standard compliance of their sort (at the bottom of this page) then it is their documentation that is wrong. You should use less_equal with it. – Camembert

@San: Your logic is backwards. sort is required to work if you do provide a strict weak ordering. If you don't provide a strict weak ordering, all requirements on it are removed. It's not required to succeed, but it's not required to fail either. – Semiautomatic

@Vilayet if all you ever do is sort elements that are all inequivalent (i.e. either x <= y or y <= x, but not both), you will get away with using <= as comparator. See also Item 19 of Scott Meyers's Effective STL ("understand the difference between equivalence and equality"). – Racemic

I have one question. Why do std::sort need to compare both a < b and b < a ? standard sorting algorithms compare one way , not both way. – Functionary

std::stable_sort would work with less than or equal to, correct? – Erratic