3

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 ?

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
san
  • 4,144
  • 6
  • 32
  • 50
  • You can sort it however you want with the custom comparator. – chris May 29 '13 at 22:05
  • 4
    @chris Are you sure ? I think the result can be undefined if the comparator is not strict weak order – san May 29 '13 at 22:06
  • @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. – syam May 29 '13 at 22:08
  • Sorry, I answered a different question than you were asking. – chris May 29 '13 at 22:09
  • It will probably still work with a usual implementation (in VC, it uses qsort, heap sort or insertion sort depending on list size). – riv May 29 '13 at 22:14
  • 1
    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. – Retired Ninja May 29 '13 at 22:15
  • @riv Heh! discovered this by getting singed on g++ by this, thought less_equals will lead to less data movement. – san May 29 '13 at 22:16
  • 2
    @RetiredNinja testing based development is ok, but knowing the correct behavior is better, after all, there only so many things that one can test. – san May 29 '13 at 22:21
  • 1
    @RetiredNinja: what makes you think you'd get an assertion or exception if it failed? – jalf May 29 '13 at 22:27
  • @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. – Retired Ninja May 30 '13 at 00:11
  • @RetiredNinja and how exactly will Visual Studio find out if the comparator is "incorrect", which in this context means violates strict weak orderedness ? – san May 30 '13 at 00:39
  • @san The rules for strict weak ordering are easy enough to validate. – Retired Ninja May 30 '13 at 01:15
  • @RetiredNinja please elaborate, am very curious. Say I have objects of class C. How does the compiler verify op(C,C) is valid. – san May 30 '13 at 03:02
  • 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 – Ranju Jul 27 '21 at 01:09

1 Answers1

7

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.

jalf
  • 243,077
  • 51
  • 345
  • 550
  • So is it so that stdcxx's sort is not standard compliant and still works with <= ? – san May 29 '13 at 22:10
  • 2
    Given that they claim standard compliance of their `sort` (at the bottom of [this page](http://stdcxx.apache.org/doc/stdlibref/sort.html)) then it is their documentation that is wrong. You should use `less_equal` with it. – jrok May 29 '13 at 22:15
  • 2
    @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. – Jerry Coffin May 29 '13 at 22:25
  • @san 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"). – TemplateRex May 30 '13 at 06:30
  • 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. – Ranju Jul 26 '21 at 08:04