6

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?

archaic
  • 85
  • 1
  • 8
  • 1
    You should use trailing underscores (or something else to distinguish these) [instead of leading underscores](http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier). – Brian Cain Sep 23 '12 at 02:38
  • 1
    @Brian: since these aren't file scope and the underscore isn't followed by an uppercase character, they're OK as far as not being reserved. Still, this area causes enough confusion that another naming convention might make some people happier. – Michael Burr Sep 23 '12 at 02:52
  • As a note - if `vals` has length 15, then `inds` had better contain indexes in the range [0..14], not [1..15]. – Michael Burr Sep 23 '12 at 04:04
  • The C++98 standard says: §17.4.3.1.2 **Global names [lib.global.names]** _Certain sets of names and function signatures are always reserved to the implementation: — Each name that contains a double underscore (`__`) or begins with an underscore followed by an uppercase letter (2.11) is reserved to the implementation for any use. — Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace._ with footnote 165 after the last bullet saying _Such names are also reserved in namespace ::std (17.4.3.1)._ I don't think the rules changed. – Jonathan Leffler Sep 23 '12 at 07:50

2 Answers2

7

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.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • Thanks Michael. I now understand what the problem is. Based on your suggestion, I found a workaround: I am now passing a vector of random numbers (of length 15) to Compare() which is used to break the tie when the two values are equal. This way the transitive and equivalence properties of Compare() hold. – archaic Sep 23 '12 at 18:34
3

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523