Sorting using lambda function in c++

Question

I don't understand what is wrong with the following simple sorting code. It compiles but produce a segmentation fault when I try to run it.

I know there are other ways of doing the same kind of sorting, and the values that I'm using are all the same (so, there's nothing to sort), but I would like to understand why it produce a segmentation fault.

There is no problem if I use w[1][i]>w[1][j] instead of w[1][i]>=w[1][j] in the comparator.

vector<int> a(100);
iota(a.begin(),a.end(),0);
vector<vector<int> >  w(2,vector<int>(100,1));
sort(a.begin(),a.end(),[&w](const int i,const int j){return w[0][i]>w[0][j] || (w[0][i]==w[0][j] && w[1][i]>=w[1][j]);});

So what were the values of `i` and `j` when it crashed? You can see exactly what happened to cause a SEGV by running under a debugger, or by dumping a core file and opening _that_ in the debugger. — Useless, Jun 12 '19 at 19:40
Greater-or-equal violates the strict weak ordering required for `std::sort`. Therefore such a comparison will invoke undefined behavior when using that algorithm. You do not (and should not) need to test for direct or partial equivalence. All you should care about overall is `is-less-than` and return true in said condition. — WhozCraig, Jun 12 '19 at 19:44
Possible duplicate of [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Raedwald, Jun 13 '19 at 12:31

score 5 · Answer 1 · answered Jun 12 '19 at 19:50

Your lambda does not provide a strict weak ordering, violating the contract the std::sort has. This means the code has undefined behavior and a segmentation fault is a possible outcome of that. With strict weak ordering if a < b is true then b < a must be false. That doesn't happen here. No matter what i and j are

w[0][i]>w[0][j] || (w[0][i]==w[0][j] && w[1][i]>=w[1][j])

turns into

1 > 1 || (1 == 1 && 1 >= 1)

which is

false || (true && true)

which is just true. If i and j (a and b) get swapped around, you still get the same result. When you use > instead of >= then 1 > 1 is false causing the lambda to return falseand sort says that all of the items are equal.

Sorting using lambda function in c++

1 Answers1