Hamzqq9's blog

Strange verdict in compare function while sorting
By Hamzqq9, history, 7 years ago, In English

I was trying to solve this problem and after coding it I got Runtime Error.

bool cmp(iiii x,iiii y) {

	int bx=x.st.st/KOK;
	int by=y.st.st/KOK;

	if(bx<by) return true;
	if(bx>by) return false;

	if(x.st.nd>y.st.nd) return false; /* this line */

	return true;

}

When I change the line shown in the code above to

if(x.st.nd>=y.st.nd) return false;

by just adding '=' chararacter It got AC.

Strangely when I debug the code before changing it, cmp function was called infinite time.

Is there a any idea why something like this happened?

Note: iiii means 

pair < pair<int,int> , pair<int,int> >
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

In C++ sort function, compare function must satisfy strict weak ordering.

http://en.cppreference.com/w/cpp/algorithm/sort

comparison function object (i.e. an object that satisfies the requirements of Compare)

http://en.cppreference.com/w/cpp/concept/Compare

For all a, comp(a,a)==false

In short, equal values must return false in C++, otherwise no guarantee it will finish/work.

https://stackoverflow.com/questions/45929474/why-must-stdsort-compare-function-return-false-when-arguments-are-equal

→ Reply