CODEWITHSUNDEEP
c++c++11
Su JK
Su JK

Reputation: 171

Segmentation fault with custom sort operator in C++

Following code, reads the input from the file. Each line in the file consists of a pair of integer and a double.

After reading the values, it is stored into a struct named PNode

#include <iostream>
#include <fstream>

#include <algorithm>
#include <vector>

struct PNode {
    int xi; 
    int ri; 
    double H;

    bool operator<(const PNode& rhs) const {
        if (ri > rhs.ri) return true;
        if (H < rhs.H) return true;
        return false;
    }   
};  

int main(int argc, char* argv[]) {

    if (argc != 2) { 
        std::cout << "usage: " << argv[0] << " input" << std::endl;
        return -1;
    }

    std::vector<PNode> v;
    std::ifstream f(argv[1]);

    int xi = -1;
    int ri = -1;
    double H = -1;

    while(f >> xi >> ri >> H) v.push_back(PNode{xi, ri, H}); 

    for (auto& x : v) std::cout << x.xi << "\t" << x.ri << "\t" << x.H << std::endl;
    std::sort(v.begin(), v.end());
    for (auto& x : v) std::cout << x.xi << "\t" << x.ri << "\t" << x.H << std::endl;

    return 0;
}

Data structure PNode has internally defined operator< to used on sorting the PNode.

However, on some inputs the code emits segmentation fault.

Failing input:

0 2 12
1 3 210.618
2 4 57.8743
3 4 155.022
4 2 8
5 4 0
6 3 90.8939
7 4 2
8 5 96.3038
9 3 95.268
10 4 650.056
11 2 32.2647
12 3 30.7549
13 2 29.2451
14 4 0
15 2 0
16 5 191.284
17 4 234.158
18 2 115.349
19 4 348.659
20 3 0
21 2 283.372
22 4 8
23 4 328.962
24 2 46.2444
25 4 2
26 3 142.561

Working input:

0 2 29.7149
1 2 441.595
2 2 25.2916
3 2 1149.05
4 2 364.557

Code has been compiled using following flags:

g++ -g3 -std=c++11 test.cpp

Executed:

valgrind --leak-check=full ./a.out IN

First few lines of error reported by valgrind:

Conditional jump or move depends on uninitialised value(s)
==26785==    at 0x4013BC: PNode::operator<(PNode const&) const (test.cpp:13)
==26785==    by 0x4027A0: bool __gnu_cxx::__ops::_Iter_less_iter::operator()<__gnu_cxx::__normal_iterator<PNode*, std::vector<PNode, std::allocator<PNode> > >, __gnu_cxx::__normal_iterator<PNode*, std::vector<PNode, std::allocator<PNode> > > >(__gnu_cxx::__normal_iterator<PNode*, std::vector<PNode, std::allocator<PNode> > >, __gnu_cxx::__normal_iterator<PNode*, std::vector<PNode, std::allocator<PNode> > >) const (predefined_ops.h:43)

Upvotes: 0

Views: 303

Answers (2)

R Sahu
R Sahu

Reputation: 206557

I agree with the comment by @Slava.

I suggest a little refinement to the function.

bool operator<(const PNode& rhs) const {
    if (ri != rhs.ri)
    {
       return (ri > rhs.ri);
    }
    return (H < rhs.H);
}

Upvotes: 3

Slava
Slava

Reputation: 44238

Your PNode::operator< does not satisfy strict weak ordering requirement.

Possible fix:

bool operator<(const PNode& rhs) const {
    if (ri > rhs.ri) return true;
    if (ri < rhs.ri) return false;

    return H < rhs.H;
}

Upvotes: 2

Related Questions