Oi.'s blog

By Oi., 9 years ago, In English,
Think you can solve it :)? We all know it is expected that contradictory comparison functions may cause Runtime Error when used by the sort method. For instance, one could try sorting an array using a function that only returns True!

However, when seemingly equivalent procedures start giving different results, curiosity strikes!
Take this example:

struct number{
    int z;
    const bool operator< (const number &that) const{
        return z <= that.z;
    }
}numbers[10000];

int main (){
    for(int i = 0; i < 10000; i++){
        numbers[i].z = 2;
    }
    sort(numbers, numbers+10000);
    return 0;
}

Note the operator<  returns <=. In some cases this would cause a Runtime Error, such as if you replaced the
"numbers[i].z = 2;" line with something like "numbers[i].z = i%10;". But we will focus on this case, on which it does not result in error.

By now you must've noticed this struct basically simulates the sorting of an integer array, except for the <= comparison. So, one would expect an int array to behave similarly, when using a similar comparison function! Yet...

int array[10000];
const bool myfunc (int a, int b){
    return a <= b;
}

int main (){
    for(int i = 0; i < 10000; i++){
        array[i] = 2;
    }
    sort(array, array+10000, myfunc);   
    return 0;
}

If you try to execute this piece of code, although it inherently seems to be doing exactly the same as the one above, a Runtime Error will occur this time. Can you guess why? :)
 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

9 years ago, # |
  Vote: I like it +10 Vote: I do not like it
The problem is with your comparison operator. It has to be anticommutative so it will define strict ordering.
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well, formally a bad predicate/operator causes undefined behavior, so both behaviors are valid. But wow, do they have different implementations for sorting with a predicate and an operator o_O? Also, how does const bool return type differ from just bool (it's value type anyway)?
  • 9 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it
    I couldn't arrive to such conclusion. On my system both codes did not produce RTEs. But if I define both arrays in same file, then both codes do produce a RTE... unless I choose smaller array sizes. So it's really just random, depending on stack size, compiler version, OS etc. I think the author's test was somehow flawed, and there is really no difference in implementation.