Why this code throws an exception Invalid comparator

#include <iostream> #include <algorithm> class StrCmp { public: template <typename T> bool operator() (const T* p1, const T* p2) const { while (*p1 && *p2 && *p1 == *p2) ++p1, ++p2; return *p2 - *p1 > 0; } }; int main(int argc, char* argv[] ) { const unsigned int* a[] { (const unsigned int*)"Сидоров", (const unsigned int*)"Петров", (const unsigned int*)"Иванов", (const unsigned int*)"Аров", (const unsigned int*)"Аро", (const unsigned int*)"", }; std::sort(a, a + 6, StrCmp() ); return 0; }

    2 answers 2

    In this case, everything is simple - you compare unsigned values, and *p2 - *p1 always greater than zero. By unsigned :)

    And Visual C ++ in the debugging mode checks the comparator, comparing two calls - of the type comp(a,b) and comp(b,a) , and if both of them are true - he rightly considers the comparator incorrect.

    For it can not simultaneously be a < b and b < a . Correct your comparator so that it gives the correct results ...

    PS Execute the following code :

     std::cout << StrCmp()(a[2],a[5]) << std::endl; std::cout << StrCmp()(a[5],a[2]) << std::endl;

    The output will be - two units. Those. and a[2] < a[5] , and a[5] < a[2] - so says your comparator.

    But this does not happen, and VC ++ (in debug mode) informs you that your comparator is no good. Because comparing a with b gives the same result as b with a ...

    • one word is wrong ... - AR Hovsepyan
    • @AnT Ah, yes, here I got excited ... - Harry
    • @Harry like that something can be both less and more - Stanislav Petrov
    • Here! No And your comparator gives you both more and less! See amended answer. - Harry

    When re-interpreting an ordinary char [] string with a single \0 at the end as an unsigned int [] array, there is almost no chance that at the end of such an unsigned int [] array you will see the trailing 0 . That is, if your comparison cycle does not find differences, then such a cycle will not stop at the end of the line, but will go beyond the limits of available memory and compare uninitialized and / or unstable values. Comparing unstable values ​​leads to unstable and / or inconsistent comparison results, which leads to unspecified behavior, including the release of such an exception.

    Reinterpretation of memory is almost always a dirty hack. But if you want to compare your lines in this way, then you need to ensure that at the end of each line there will be a null value of type unsigned int . For example, with sizeof(unsigned int) == 4 your lines should look like

     const unsigned int* a[] { (const unsigned int*)"Сидоров\0\0\0\0\0\0", (const unsigned int*)"Петров\0\0\0\0\0\0", (const unsigned int*)"Иванов\0\0\0\0\0\0", (const unsigned int*)"Аров\0\0\0\0\0\0", (const unsigned int*)"Аро\0\0\0\0\0\0", (const unsigned int*)"\0\0\0\0\0\0", };

    Those. in general (without adjusting to the length of a particular line) you need at least 7 zeros at the end of the line to ensure that re-interpreting this line as unsigned int [] will find a null value at the end.

    • why will it go beyond the limits of available memory - Stanislav Petrov
    • @Stanislav: You re-interpret the char array as an unsigned int array. On "normal" platforms, unsigned int larger than char . At the end of the original char array is a lone char equal to 0 . But there are very few chances for a miraculous unsigned int , equal to 0 . For this reason, if the source arrays of strings are equal, your cycle will almost never end, but will fly out of the array and cover there with a copper basin. Eg: coliru.stacked-crooked.com/a/83662a1d1a5a88ab - AnT