Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

clang standard library bug or c++ undefined behavior?

Does the following C++ program contain any undefined behavior?

int
main()
{
        struct entry
        {
                uint32_t hash;
                uint32_t idx;
        };
        entry arr[31] = {
            {   7978558,  0}, {   9241630,  1}, {  65706826,  2},
            { 639636154,  3}, {1033996244,  4}, {1225598536,  5},
            {1231940272,  6}, {1252372402,  7}, {2019146042,  8},
            {1520971906,  9}, {1532931792, 10}, {1818609302, 11},
            {1971583702, 12}, {2116478830, 13}, { 883396844, 14},
            {1942092984, 15}, {1274626222, 16}, { 333950222, 17},
            {1265547464, 18}, { 965867746, 19}, {1471376532, 20},
            { 398997278, 21}, {1414926784, 22}, {1831587680, 23},
            { 813761492, 24}, { 138146428, 25}, { 337412092, 26},
            { 329155246, 27}, {  21320082, 28}, {1751867558, 29},
            {1155173784, 30},
        };

        std::sort(std::begin(arr), std::end(arr),
                  [](entry a, entry b) { return a.hash <= b.hash; });
}

When I compile with gnu c++ compiler or any clang/llvm after 12.0.0, the program works fine. However, when I compiled it with clang version 12.0.0 (the default compiler shipped on my Mac laptop), it crashed inside of std::sort() as following:

$ g++ --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.0 (clang-1200.0.32.2)
Target: x86_64-apple-darwin21.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
$ g++ -g -std=c++11 bug.cc
$ ./a.out
Segmentation fault: 11

Also if I change it to use std::vector instead of fixed size array. The std::sort() will never return when compiled with clang 12.0.0

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

Yes, the comparator is not a strict weak ordering which violates the preconditions of std::sort, resulting in undefined behavior.

For two arguments a and b (possibly identical), a strict weak ordering comp should never evaluate both comp(a,b) and comp(b,a) to true. In other words, it should model the behavior of the built-in <, not <=.

So in your code it should be <, not <=, to make it a strict weak ordering.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading