CODEWITHSUNDEEP
c++
user17336748
user17336748

Reputation:

C++ - Code crashes when trying to sort 2d vector

I'm writing a code in C++ and it's always giving the same error: Segmentation Fault, but I don't know why this is happening. I've created a small program that gives the error.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int N = 17;
vector<vector<int>> v;
void func(vector<int>& x){
    for(int i = 0; i < N; i++){
        v.push_back(vector<int>(x));
    }
}

int main(){

    int n = 5;
    vector<int> v2(n, 0);
    func(v2);
    cout << v.size() << endl; // prints 17

    sort(v.begin(), v.end(), [&n](const auto &a, const auto &b){
        for(int i = 0; i < n; i++)
            if(a[i] != b[i]) return a[i] < b[i]; 
        return true;
    });

    return 0;
}

The function func is supposed to do a recursive computation. I pass v2 by reference because I push and pop elements from it. When I got to a certain point in recursion, I add it to the global 2d vector v.

My code's working to every test case I tried except this one.

The fun thing is that the programs works with no error when N < 17.

The error is happening at the lambda sort. There is an 'a' that breaks the code. Even if erase the for loop, it still crashes.

I know that using global variable is bad, but in competitive programming this is a common practice.

I'm compiling with the following:

g++ test.cpp && ./a.out

My g++ version:

(Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

EDIT: Thanks to @DrewDormann, I managed to fix it.

Just changing the return of the lambda function to false instead of true.

Upvotes: 0

Views: 84

Answers (1)

Acorn
Acorn

Reputation: 26066

std::sort requires irreflexivity. From [alg.sorting] in the standard:

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x)

However, the lambda returns true for comp(x, x).

The fun thing is that the programs works with no error when N < 17.

It's undefined behavior. It's unlucky if it works by chance.

Upvotes: 1

Related Questions