Geek asks and answers

C ++ std :: vector std :: sort infinite loop

I ran into a problem every time I tried to sort a vector of objects, which led to an infinite loop. I use a custom comparison function that I passed to the sort function.

I was able to fix the problem by returning false when the two objects were equal instead of true, but I do not quite understand the solution. I think this is because my comparison function violated this rule, as indicated on cplusplus.com:

The object of the comparison function, which, taking two values ​​of the same type than those contained in the range, returns true if the first argument before the second argument in a specific strict weak order determines false otherwise.

Can someone provide a more detailed explanation?

+3
source share
6 answers

The correct answer, as others have pointed out, is to find out what a "strict weak order" is. In particular, if comp(x,y)true, then it comp(y,x)must be false. (Note that this means it comp(x,x)is false.)

This is all you need to know to fix your problem. The algorithm sortdoes not do promises at all if your comparison function breaks the rules.

, , sort, , quicksort . Quicksort " " . , a, b " ", , b, a " ", .

+5

, " ", : Order Say!

, .

+6

, . , false .

+6

++, 25.3[lib.alg.sorting]/2

Compare , true, , false .

, , " ".

+3

, , A < B B < A, . , A B, .

+1

Strict weak ordering means <b == true, and when you return true for equality, its a <= b == true. This requirement is necessary for optimality for different sorting algorithms.

0
source

More articles:


All Articles