C++

Forum

 
Program to sort data crashes, don't know why

Ganado (6786)
This is my program:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

struct Foo {

    int version {};
    long long seconds {};
    int process {};
    int sequence {};
    
    friend bool operator<(const Foo& lhs, const Foo& rhs)
    {
        return
          (lhs.version  < rhs.version) ? true :
          (lhs.seconds  < rhs.seconds) ? true :
          (lhs.process  < rhs.process) ? true :
          (lhs.sequence < rhs.sequence);
    }
    
    friend std::istream& operator>>(std::istream& in, Foo& foo)
    {
        char separator;
        in >> foo.version  >> separator
           >> foo.seconds  >> separator
           >> foo.process  >> separator
           >> foo.sequence;
        return in;
    }
    
    friend std::ostream& operator<<(std::ostream& out, const Foo& foo)
    {
        const char separator = '.';
        out << foo.version  << separator
            << foo.seconds  << separator
            << foo.process  << separator
            << foo.sequence;
        return out;
    }
};

int main()
{
    std::vector<Foo> foos;
    Foo foo;
    while (std::cin >> foo)
    {
        foos.push_back(foo);
    }

    std::sort(foos.begin(), foos.end());
    
    for (const auto& foo : foos)
    {
        std::cout << foo << '\n';
    }
}


I am compiling with:
g++ -Wall -Wextra -Wpedantic -g prog.cpp -o prog


My compiler is MinGW 64-bit:
g++ (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0


My program crashes when I do the following:
type min_example.txt | prog
(using cat instead of type produces same response)

min_example.txt is as follows:
1.63742117468.30756.842
1.63742117468.30756.850
1.63742117468.30756.82
1.63742117468.30756.858
1.63742117468.30756.866
1.63742117468.30756.874
1.63742117468.30756.882
1.63742117468.30756.890
1.63742117468.30756.898
1.63742117468.30756.906
1.63742117468.30756.914
1.63742117468.30756.922
1.63742117468.30756.930
1.63742117468.30756.90
1.63742117468.30756.938
1.63742117468.30756.946
1.63742117468.30756.954
1.63742117468.30756.962
1.63742117468.30756.970
1.63742117468.30756.978
1.63742117468.30756.986
1.63742117468.30756.994
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
(note: Same issue regardless of file ending with a newline)

Running the debugger shows:
>gdb prog
GNU gdb (GDB) 8.1
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-w64-mingw32".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from prog...done.
(gdb) run < min_example.txt
Starting program: [redacted]\prog.exe < min_example.txt
[New Thread 13624.0x2a64]
[New Thread 13624.0x8cc]
[New Thread 13624.0x3d0c]
[New Thread 13624.0x320]
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
1.63742350331.23832.16086
-17891602.-76843841185972498.793867558.805456004
1.63742117468.30756.82
1.63742117468.30756.90
1.63742117468.30756.842
1.63742117468.30756.850
1.63742117468.30756.858
1.63742117468.30756.866
1.63742117468.30756.874
1.63742117468.30756.882
1.63742117468.30756.890
1.63742117468.30756.898
1.63742117468.30756.906
1.63742117468.30756.914
1.63742117468.30756.922
1.63742117468.30756.930
1.63742117468.30756.938
1.63742117468.30756.946
1.63742117468.30756.954
1.63742117468.30756.962
1.63742117468.30756.970
1.63742117468.30756.978
1.63742117468.30756.986
1.63742117468.30756.994
warning: Critical error detected c0000374

Thread 1 received signal SIGTRAP, Trace/breakpoint trap.
0x00007fff7e8c759f in ntdll!RtlIsNonEmptyDirectoryReparsePointAllowed () from C:\Windows\SYSTEM32\ntdll.dll
(gdb)
(gdb) where
#0  0x00007fff7e8c759f in ntdll!RtlIsNonEmptyDirectoryReparsePointAllowed () from C:\Windows\SYSTEM32\ntdll.dll
#1  0x00007fff7e8cdd9a in ntdll!RtlpNtSetValueKey () from C:\Windows\SYSTEM32\ntdll.dll
#2  0x00007fff7e874eb2 in wcstok_s () from C:\Windows\SYSTEM32\ntdll.dll
#3  0x00007fff7e888b94 in ntdll!memset () from C:\Windows\SYSTEM32\ntdll.dll
#4  0x00007fff7b83995c in msvcrt!free () from C:\Windows\System32\msvcrt.dll
#5  0x0000000000402e80 in __gnu_cxx::new_allocator<Foo>::deallocate (this=0x62fe10, __p=0x25434d0)
    at C:/mingw64/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/ext/new_allocator.h:125
#6  0x000000000040369b in std::allocator_traits<std::allocator<Foo> >::deallocate (__a=..., __p=0x25434d0, __n=32)
    at C:/mingw64/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/alloc_traits.h:462
#7  0x0000000000403582 in std::_Vector_base<Foo, std::allocator<Foo> >::_M_deallocate (this=0x62fe10, __p=0x25434d0, __n=32)
    at C:/mingw64/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_vector.h:304
#8  0x000000000040360f in std::_Vector_base<Foo, std::allocator<Foo> >::~_Vector_base (this=0x62fe10, __in_chrg=<optimized out>)
    at C:/mingw64/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_vector.h:285
#9  0x0000000000403c51 in std::vector<Foo, std::allocator<Foo> >::~vector (this=0x62fe10, __in_chrg=<optimized out>)
    at C:/mingw64/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_vector.h:570
#10 0x0000000000401679 in main () at prog.cpp:45


Suffice to say, I have no idea why this is crashing. I don't see where undefined behavior could be. Anyone have an idea? Would anyone want to try this on a different compiler to see if it crashes as well?

Edit: Despite gdb saying the issue happens on prog.cpp:45, the issue actually happens at the destructor of vector (end of main), but you can see that junk data is being printed before the crash itself.

Edit 2: Crash does not happen if I do not sort the data. Is my < operator wrong? Is something going wrong with the compiler-generated copy constructors?
Last edited on
Peter87 (11179)
Yep, the problem is your < operator.
Ganado (6786)
Thank you Peter, I took a closer look after you said that... and changed it to
1
2
3
4
5
6
7
8
9
 
    // Edit: BAD CODE - DO NOT USE
    friend bool operator<(const Foo& lhs, const Foo& rhs)
    {
        return
          (lhs.version  < rhs.version) ? true : (
          (lhs.seconds  < rhs.seconds) ? true : (
          (lhs.process  < rhs.process) ? true : (
          (lhs.sequence < rhs.sequence))));
    }

You can tell I have rarely, if ever, used nested ternary operators.
I should probably just stick to if/else.
Last edited on
Peter87 (11179)
Ternary operators are probably not the right approach. Yes, if lhs.version < rhs.version is true you want to return true but if lhs.version > rhs.version is true you definitely want to return false but right now you instead go on and compare other values which might end up returning either true or false. This is likely to lead to an inconsistent ordering.

It would normally look more like the following:
1
2
3
4
5
6
7
8
9
10
11
 
if (lhs.version != rhs.version)
{
	return lhs.version < rhs.version; 
}

if (lhs.seconds != rhs.seconds)
{
	return lhs.seconds < rhs.seconds; 
}

...
Last edited on
Ganado (6786)
I see what you mean about inconsistent ordering, although I still don't understand the operator precedence with the ternary operator. Would you mind showing me how the compiler was evaluating my first post's < operator? I tried to add my own parentheses but now I'm just getting syntax errors.

Regardless of my misunderstanding of the ternary operator, I have now changed my function to the following, from your advice:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
    
    friend bool operator<(const Foo& lhs, const Foo& rhs)
    {
        if (lhs.version != rhs.version)
            return lhs.version < rhs.version;
        
        if (lhs.seconds != rhs.seconds)
            return lhs.seconds < rhs.seconds;
        
        if (lhs.process != rhs.process)
            return lhs.process < rhs.process;
        
        return lhs.sequence < rhs.sequence;
    }
Last edited on
Ganado (6786)
Nevermind, I figured it out. Both this post and my second post crash.
I had forgotten to uncomment the sort xD
1
2
3
4
5
6
7
8
9
 
    // BAD CODE - DO NOT USE
    friend bool operator<(const Foo& lhs, const Foo& rhs)
    {
        return
          ((((lhs.version  < rhs.version) ? true :
          (lhs.seconds  < rhs.seconds)) ? true :
          (lhs.process  < rhs.process)) ? true :
          (lhs.sequence < rhs.sequence));
    }


Everything works with the != if-chain. Thanks again for the help.
Last edited on
Peter87 (11179)
I think you got the precedence right. Your first attempt should be equivalent to your second attempt. The problem was just that the logic was not correct. If rewritten using if statements it would look something like the following ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
if (lhs.version < rhs.version)
{
	return true;
}
else if (lhs.seconds < rhs.seconds)
{
	return true;
}
else if (lhs.process < rhs.process)
{
	return true;
}
else
{
	return lhs.sequence < rhs.sequence;
}

... which is obviously not correct.
Peter87 (11179)
Now that I think about it some more I realize you can of course write it using ternary operators ...

1
2
3
4
 
return lhs.version != rhs.version ? lhs.version  < rhs.version : 
       lhs.seconds != rhs.seconds ? lhs.seconds  < rhs.seconds : 
       lhs.process != rhs.process ? lhs.process  < rhs.process : 
                                    lhs.sequence < rhs.sequence;

... but I personally like the if statements more.
Last edited on
Ganado (6786)
Yep, agreed.
ElusiveTau (147)
I ran the code in your original post with just 2 lines from the data file:

1
2
 
Line #1: 1.63742117468.30756.842
Line #2: 1.63742350331.23832.16086


and get an error. The root of the problem is the logic behind the conditional expressions, which you've corrected, but while step-debugging through std::sort(), I noticed it ran your < operator overload twice for just 2 items: first time where lhs = Line #2 and rhs = Line #1 and the second time where lhs = Line #1 and rhs = Line #2.

The chained ternary expressions in your OP does return either true or false but it seems the error was thrown because of the way std::sort() calls the operator overload to determine object ordering.

For the comparison B < A, where A is Line #1 and B is Line #2, std::sort() checks B < A and also A < B. It expects A < B to be false if the initial comparison B < A returns true (which it does, even though it's incorrect, assuming your intent was to have it compare by version, then by seconds, etc.), indicating that "B is less than A"/"B comes before A". By the definition of your overload, however, the second check, A < B, also returns true -- a contradiction! So it throws an error.

This is what I observe, step debugging through in Visual Studio (which I think is using the Visual C++ compiler)
Last edited on
Ganado (6786)
You're absolutely correct. I kept halving my input data in two until I didn't get a crash, but I didn't bother to see which specific pieces of the data were causing the issue. As you detailed, in my bad code, for #1 < #2, (lhs.seconds < rhs.seconds) evaluates to true, and it returns true. But for #2 < #1, (lhs.process < rhs.process) evaluates to true, and so it also returns true.

In C++ terms, the undefined behavior comes from the requirements for Compare not being fulfilled.
28.7.3
For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 28.7.3, comp shall induce a strict weak ordering on the values.

https://en.cppreference.com/w/cpp/named_req/Compare
https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings
Here it fails the, "For all x, y in S, if x < y then it is not the case that y < x (asymmetry)." part.
Last edited on
Topic archived. No new replies allowed.