All you should know about comparators in C++

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Please put to main page. So we won't see blogs like https://codeforces.net/blog/entry/70236 in the nearest future.

In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.

Hope you remember it and will never make such a stupid mistake!

Comments (29)

Show archived | Write comment?

kpw29

5 years ago, # |

-16

I didn't know about this before xD

What happens if you return true instead? Runtime error always? Probably not.

→ Reply

rotavirus

5 years ago, # ^ |

+52

runtime error sometimes

PHOENIX_5

4 years ago, # ^ |

+34

and TLE sometimes

dorijanlendvaj

+19

and MLE sometimes

Not-Afraid

& segmentation fault sometimes

+23

That's just one form of runtime error, which was already mentioned.

Okay sir.

+14

adam_rajsky

lis05

3 years ago, # ^ |

-20

and CE sometimes

AnandOza

What's an example where this leads to MLE?

+10

30440158

That's pretty rare(resubmitting just gave RE on a later test case) but it did happen to me once.

Ausmosian

Learned it the hard way!!

TLE/RE -> atcoder_26299668

AC -> atcoder_26323495

Abito

23 months ago, # ^ |

-18

and compilation error sometimes

Rating1729

3 months ago, # ^ |

← Rev. 3 →

Didn't get the reasons for having RE, MLE and TLE respectively. Appreciate if someone could elaborate for dumb me.

UPD: Reading the discussion in this comment: https://codeforces.net/blog/entry/70358?#comment-548342, I get why it can potentially give TLE by entering a loop of swapping a and b when a=b, but still not clear on MLE and RE part.

UPD2: Further reading this https://stackoverflow.com/a/56898410 describes how it the partition function in internal implementation of sort can lead to Runtime Error.

I'm not exactly sure what leads to each of those, but when you do something that is undefined behavior you should expect anything to be able to happen.

dalex

← Rev. 2 →

https://codeforces.net/blog/entry/70358?#comment-548342 by nishant403

AmineTrabelsi

It's sad that you only see this kind of posts after you get wrong answer.
Why isn't this mentioned in tutorials, the only way to know about this is to read the documentation.(or blogs like this which you can never find without searching for)

+31

You are supposed to read documentation for the function BEFORE using this function

ouuan

← Rev. 4 →

+44

That's not all you should know about it.

In fact, it should be a Strict Weak Ordering.(transitivity and transitivity of equivalence are also needed).

There's a well-known problem which can be solved by Johnson's rule, and a simple greedy solution which sorts the jobs lacks of transitivity of equivalence. The wrong comparator is $$$P(i, j)=\min(a_i,b_j)<\min(a_j,b_i)$$$ , it should be $$$P(i, j)=\begin{cases}a_i< a_j&\min(a_i,b_j)=\min(a_j,b_i)\\min(a_i,b_j)<\min(a_j,b_i)&\text{otherwise}\end{cases}$$$ .

I don't know any English material about this problem except Wikipedia, so here is this problem in Chinese. In this article (also in Chinese) written by me, I discussed about it.

If anyone is interested in it, I can write a blog about it (in English) :)