Always use strict weak ordering('<') in std::sort custom comparison function

Правка en1, от i_am_pikachu, 2026-01-11 08:10:21

Code 1:

sort(all(edges), [&] (pair<int, int>& a, pair<int, int>& b) {
    return ((val[a.first]+val[a.second]) <= (val[b.first]+val[b.second]));
});

Code 2:

sort(all(edges), [&] (pair<int, int>& a, pair<int, int>& b) {
    return ((val[a.first]+val[a.second]) < (val[b.first]+val[b.second]));
});

These were a part of my solution to 2176D - Fibonacci Paths. The first code gave me runtime error on test case 8 but the later one is AC.

std::sort requires strict weak ordering, which means when comparing two equal objects the custom comparison function must return false. The reason for this being, under the hood std::sort uses < operator by default to compare two objects when no custom comparison function is given, hence when we do provide a custom function std::sort expects it to behave similar to the < operator. Using <= violates this expectation.

Теги sort, custom comparator

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский i_am_pikachu 2026-01-11 08:10:21 1066 Initial revision (published)