All you should know about comparators in C++

№	Пользователь	Рейтинг
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

№	Пользователь	Вклад
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
4	Um_nik	143
6	Errichto	139
7	adamant	137
8	BledDest	134
9	maroonrk	133
10	qwexd	130

Please put to main page. So we won't see blogs like https://codeforces.me/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!

Комментарии (34)

Показать архивные | Написать комментарий?

kpw29

7 лет назад, скрыть # |

-16

I didn't know about this before xD

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

→ Ответить

rotavirus

7 лет назад, скрыть # ^ |

+52

runtime error sometimes

PHOENIX_5

6 лет назад, скрыть # ^ |

+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

5 лет назад, скрыть # ^ |

-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

4 года назад, скрыть # ^ |

-18

and compilation error sometimes

Rating1729

2 года назад, скрыть # ^ |

← 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.me/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.me/blog/entry/70358?#comment-548342 by nishant403

ecemekici

I dont know how any of us survived this far without knowing this.

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) \lt \min(a_j,b_i)$$$ , it should be $$$P(i, j)=\begin{cases}a_i \lt a_j&\min(a_i,b_j)=\min(a_j,b_i)\\min(a_i,b_j) \lt \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) :)

breddreamer

I will be grateful if you write the blog in english, thanks.

See this.

I didn't translate that Chinese blog. I wrote a new one instead :)

SAURAV555

5 лет назад, скрыть # |

Thanks to this blog!!

But I don't understand what's the reason behind it & why it's run for small values not for larger ones

purplesyringa

But I don't understand what's the reason behind it

Because when the sorting function wants to check if a and b compare equal, it checks !lt(a, b) && !lt(b, a) where lt is your comparator.

One thing you should know about comparators — Strict Weak Ordering

onebit1024

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

Yoks1729-

True

Saul-Goodman

4 года назад, скрыть # |

-10

Or just use pairs of pairs of pairs, and negative numbers to find a way to use the default comparator.

iamnick

3 года назад, скрыть # |

sarvagya2545

3 года назад, скрыть # ^ |

Looks like something I will forget anyways :(

OtterZ

2 года назад, скрыть # |

A good warning,but it may not necessary to repeat so many times.

d3v4n5h

4 месяца назад, скрыть # ^ |

when someone gets a WA after trying for so long, this happens

_Santiago_

19 месяцев назад, скрыть # |

Thank you for this blog. I will not forget it in the future. I was trying to solve a recent contest problem using custom sort.

problem link — https://codeforces.me/contest/2063/problem/C

I think when the two arguments are equal does it matter to return true or false? So I returned true (use a <= b) and got RTE. Then, I tried to find out why I got RTE and found this blog and some more. Although they helped me to solve the RTE but I didn't understand it properly. I follow a rule, when I try to learn something I try to learn it properly understand the process step by step, and prove it. But sometimes I could not understand that properly and I skipped it. I believe in my level I will not be able to understand it 100 percent. So rather than prove the process I just accept it and use it. What are you guys doing in that case when you cannot understand what are you trying to learn? Maybe it is far far advanced from your level.

Блог пользователя dalex