Invalid < operator assertion in sort

Question

I am trying to implement a simple comparator for sorting indices based on values in an array "_vec". I am getting an "invalid < operator" run-time error message. I fail to understand what is wrong with the following code:

class Compare{
vector<int>& _vec;
public:
    Compare(vector<int>& vec) : _vec(vec) {}
    bool operator()(size_t i, size_t j){
        if(_vec[i] != _vec[j])
        return _vec[i] < _vec[j];
        else
        return (double)rand()/RAND_MAX < 0.5; 
    }
};

I am using the following function call:

sort(inds.begin(),inds.end(),Compare(vals));

where inds is just an array containing indices from 1 to 15 (say) and vals is the array of length 15 with some values whose sorted indices I want to compute. The overall goal is to randomize the sort order when two (or more) entries in vals are equal. Any help?

Answer 1

std::sort expects your less-than operator to supply a transitive relationship, i.e. when the sort sees A < B is true and B < C is true, it implies that A < C is true as well.

In your implementation, the transitivity rule does not hold: when two items are equal, you randomly tell the sort that one of them is greater than the other. This triggers the debug assertion.

Return false for equal values to fix this.

Answer 2

std::sort() expects the comparison operation to be stable - if a particular result is returned when two items are compared, the comparison must return the same result if those items are compared again later. When you return a random value, obviously that's not necessarily going to hold.

C++03 25.3/4 "Sort and related operations" says:

If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

• comp(a, b) && comp(b, c) implies comp(a, c)
• equiv(a, b) && equiv(b, c) implies equiv(a, c)

[Note: Under these conditions, it can be shown that

• equiv is an equivalence relation
• comp induces a well-defined relation on the equivalence classes determined by equiv
• The induced relation is a strict total ordering.

—end note]

And for clarification, Table 28 defines an equivalence relation:

== is an equivalence relation, that is, it satisfies the following properties:

• For all a, a == a.
• If a == b, then b == a.

So your Compare() operation will not produce an equivalence relation.

It's kind of nice to get an assertion rather than losing data randomly.

One way to solve the problem of randomizing the sort order when two (or more) entries in _vec are equal is to make up a random value for those indexes and keep track of those random values in a map of index => random value or something. Just make sure that you keep track of and use those random values in such a way that the transitive and equivalence properties of Compare() hold.