-2

Allowing only Strict Weak Ordering (or only Non-Strict Weak Ordering) lets us to order a group of elements as well as find equivalent elements among them. The second part is important in implementing sets and maps. Hence there it is ok to allow only SWO (or only NSWO). (NSWO is a total ordering unlike SWO which is a partial ordering).

But if we just want to sort a group of elements, then allowing either would still work as both answer the question 'does this order before that?'. I tried providing NSWO comparator to std::sort and it was still able to sort elements correctly.

But C++ standard require comparator to always follow SWO. Why So? Is there any caveats in letting both kind of comparators to sort function?

Examples of SWO comparator are std::less, std::greater etc. Examples of NSWO comparator are std::less_equal, std::greater_equal etc.

I was looking at the attached question. 1 This question was just talking about partial orders whereas I'm talking about total order. 2 This question asks for the cause of the crash and answers explain the cause and when it can happen. Doesn't talk about why SWO was used in first place. These justifies opening my question I think.

Sourav Kannantha B
  • 2,860
  • 1
  • 11
  • 35
  • 2
    See https://stackoverflow.com/questions/48972158/crash-in-stdsort-sorting-without-strict-weak-ordering – 273K Jul 05 '23 at 17:34
  • 3
    For most practical purposes, SWO and NSWO are equivalent, so supporting both would require extra work without gaining any utility. In particular, you can simulate NSWO using SWO `a <= b` == `!(b – Jerry Coffin Jul 05 '23 at 17:38
  • @JerryCoffin True. What about other total orders? – Sourav Kannantha B Jul 05 '23 at 18:25
  • Total ordering is basically just weak ordering where equivalence implies equality. From the C++ perspective, that's pretty much a "don't care". If you want to do something strange where (for example) odd numbers compare normally, but even numbers compare as less than odd, but all equal to each other, `std::sort` has no way of knowing or caring about it. – Jerry Coffin Jul 05 '23 at 18:57
  • 1
    Sort need a SWO, for example `double` can be sorted. An algorithm using NSWO may fail if there are NaNs in the sequence of `double` because NaN compare different to all including itself. NaN equivalent to nothing is not an issue and can be sorted with SWO where equivalence is not needed. – dalfaB Jul 05 '23 at 19:07
  • @273K -- that's not what this question is about. – Pete Becker Jul 05 '23 at 19:20
  • @dalfaB I was under impression that sorting NaNs is UB even now. – HolyBlackCat Jul 05 '23 at 19:25
  • @PeteBecker Of course after the question has been edited. – 273K Jul 05 '23 at 19:29
  • @273K -- and before the edits. Should not have been closed in the first place. – Pete Becker Jul 05 '23 at 20:16
  • _2 This question asks for the cause of the crash and answers explain the cause and when it can happen. Doesn't talk about why SWO was used in first place._ - to make it possible to use effective [algorithms](https://stackoverflow.com/a/48975345/4074081) – dewaffled Jul 05 '23 at 23:31
  • There is nothing stopping you using NSWO, since all NSWO orderings are also SWO orderings. I'm not aware offhand of any algorithms in (math, computer science, etc) literature that offers a benefit (e.g. reduced complexity of sorting) from requiring NSWO. If future research finds an algorithm that offers a benefit by accepting additional restrictions, then suitable requirements can be added to a future C++ standard. – Peter Jul 06 '23 at 02:06
  • @Peter What about reverse? Does SWO offer any benefit over NSWO? If both are same, then NSWO feels more intuitive as equivalence is defined by `comp(a,b) && comp(b,a)` whereas in SWO it is reverse `!comp(a,b) && !comp(b,a)`. – Sourav Kannantha B Jul 06 '23 at 08:11
  • @dewaffled NSWO also works with those algorithms as well as TO. Does SWO gives any benefit over others or is it just what they choose of all choices? – Sourav Kannantha B Jul 06 '23 at 08:17
  • @SouravKannanthaB read the [description](https://stackoverflow.com/questions/48972158/crash-in-stdsort-sorting-without-strict-weak-ordering/48975345#48975345) why the implementation can crash - with SWO it can make assumptions to skip extra checks and comparations. – dewaffled Jul 06 '23 at 09:43

1 Answers1

0

In the case of Visual Studio, std::sort is a hybrid insertion sort | Hoare partition scheme quicksort. Hoare partition scheme relies on a std::less than type comparator to avoid having to check for going past the bounds of a partition (a release build won't include bounds checks, a debug build will include the checks). My guess is that a release build will fail in the simple case where there are more than 32 elements (the threshold for insertion sort) and all of the elements equal to each other.

rcgldr
  • 27,407
  • 3
  • 36
  • 61