Блог пользователя Oi.

Автор Oi., 13 лет назад, По-английски
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? :)
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Yes, because in your operator a<a. It's bad thing, think :)
If your operator< is incorrect, sort, lower_bound and other STL structures can crash.
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
The problem is with your comparison operator. It has to be anticommutative so it will define strict ordering.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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)?
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится
    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.