0
#include<iostream>
#include<algorithm>
#include <vector>
#include <iterator>


using namespace std;

struct PAIR { int first; int second; };

std::ostream& operator<<(std::ostream& os, const PAIR& rec)
{
    os << "(" << rec.first << ", " << rec.second << ")";
    return os;
}

bool fun(const PAIR& x, const PAIR& y) { return x.first < y.first; }

int main()
{
    vector<PAIR > v{ {1,3},{2,3}, {1,0}, {1,5} };
    auto x1 = v;
    cout << "v: ";
    std::copy(v.begin(), v.end(), ostream_iterator< PAIR >(cout, ", "));
    cout << "\n";
    cout << "sorting now\n";
    std::sort(v.begin(), v.end(), fun);
    cout << "v: ";
    std::copy(v.begin(), v.end(), ostream_iterator< PAIR >(cout, ", "));
    cout << "\n";
}

output: v: (1, 3), (2, 3), (1, 0), (1, 5), sorting now v: (1, 3), (1, 0), (1, 5), (2, 3),

Changing bool fun(const PAIR& x, const PAIR& y) { return x.first < y.first; } to bool fun(const PAIR& x, const PAIR& y) { return x.first <= y.first; } is failing during runtime.

I have just changed < to <= in function fun(). Looks like there is some prerequisite for comparison function that we pass to STL sort algorithm.

Any help or pointers is greatly appreciated. Thanks in advance.

Raghu Ram
  • 59
  • 4
  • What do you mean by "failing during runtime"? – UnholySheep Dec 22 '21 at 22:17
  • 3
    Does this answer your question? [c++ custom compare function for std::sort()](https://stackoverflow.com/questions/16894700/c-custom-compare-function-for-stdsort) – R2RT Dec 22 '21 at 22:19
  • 1
    Your function does not impose a [strict weak ordering](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings), as is required. – JohnFilleau Dec 22 '21 at 22:19
  • @UnholySheep I am using Visual Studio. Program is crashing with the following error. 'ConsoleApplication3.exe' (Win32): Loaded 'C:\Users\pc\source\repos\ConsoleApplication3\Debug\ConsoleApplication3.exe'. Symbols loaded. 'ConsoleApplication3.exe' (Win32): Loaded 'C:\Windows\SysWOW64\ntdll.dll'. 'ConsoleApplication3.exe' (Win32): Loaded 'C:\Windows\SysWOW64\kernel32.dll'. 'ConsoleApplication3.exe' (Win32): Loaded 'C:\Windows\SysWOW64\KernelBase.dll'. 'ConsoleApplication3.exe' (Win32): Loaded 'C:\Windows\SysWOW64\msvcp140d.dll'. .... The thread 0x4f08 has exited with code 0 (0x0). – Raghu Ram Dec 22 '21 at 22:22
  • There's no mention of any crash or other exception in that output you copied – UnholySheep Dec 22 '21 at 22:25
  • @JohnFilleau Thank you very much. Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself. Compare function f must satisfy the following. Irreflexivity f(x, x) must be false. My function fails here itself. Antisymmetry f(x, y) implies !f(y, x) Transitivity f(x, y) and f(y, z) imply f(x, z). – Raghu Ram Dec 22 '21 at 22:33
  • Just a style note: any reason you defined `fun` rather than simply overloading `operator<` for two `const PAIR&`? – Chris Dec 22 '21 at 22:43
  • @UnholySheep Program: I have just started with Visual studio. Upon checking it well I see the following. ...ource\repos\ConsoleApplication3\Debug\ConsoleApplication3.exe File: C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\xutility Line: 632 Expression: invalid comparator For information on how your program can cause an assertion failure, see the Visual C++ documentation on asserts. – Raghu Ram Dec 22 '21 at 22:52
  • @Chris I wanted to see how stable_sort behaves if I give my own comparator. My doubt was how stable_sort will know two values are same. All I was giving is one comparator function. I thought If I give <= it would swap without preserving order. But in my case before trying out stable_sort , sort itself has failed. – Raghu Ram Dec 22 '21 at 22:56

1 Answers1

2

Is there any prerequisite for compare function that we pass to sort algorithm in c++ STL?

Yes. It must satisfy the requirements of the Compare concept.

I have just changed < to <= in function fun().

After that change, the function doesn't satisfy the requirements of Compare concept, and the behaviour of the program is undefined.

eerorika
  • 232,697
  • 12
  • 197
  • 326