OneRaynyDay - 1 year ago 59

C++ Question

** Edit: The default constructor is not causing the issue. I have stated the reason below. I have flagged and voted to close this question, apologies for anyone who chances by this post for now. **

`int n = numCourses;`

vector<pair<int, unordered_set<int>>> graph(n, make_pair(0, unordered_set<int>())); // pair of how many edges go in, and set of its neighbors.

// We have to find our leaves:

bool leaf[n];

for(int i = 0; i < n; i++){

leaf[i] = true;

}

for(auto p : prerequisites){

graph[p.first].first++;

graph[p.first].second.insert(0);

leaf[p.second] = false;

}

vector<int> leaves;

for(int i = 0; i < n; i++){

if(leaf[i])

leaves.push_back(i);

}

I'm trying to construct a DAG graph that has some nice properties. I wanted to supply a default constructor argument into the graph, using make_pair to give the rvalue definition into the second argument of graph. The first argument is the size of the vector. I wanted to pass an rvalue where the pair's first value is 0, so I know for sure it's 0 when I increment in

`graph[p.first].first++`

I tried this and when it gets to

`graph[p.first].second.insert(0)`

`int n = numCourses;`

vector<pair<int, unordered_set<int>>> graph(n); // NO MORE DEFAULT RVALUE

// We have to find our leaves:

bool leaf[n];

for(int i = 0; i < n; i++){

leaf[i] = true;

}

for(auto p : prerequisites){

graph[p.first].first++;

graph[p.first].second.insert(0);

leaf[p.second] = false;

}

vector<int> leaves;

for(int i = 0; i < n; i++){

if(leaf[i])

leaves.push_back(i); // This causes a segfault if I don't change it.

}

So the issue was actually on the line right after

`graph[p.first].second.insert(0)`

Thank you!

EDIT: below I have added some runnable cases:

Doesn't cause segfault: https://ideone.com/EdmSva

Does cause segfault: https://ideone.com/GHQfog

It was due to the boolean array accessing out of bounds. I should've picked up on that, but

Answer Source

Yes, you are missing something - the segfault is not related to the initialization of `graph`

which works exactly as one would expect it to. Simple example to check out:

```
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int main() {
// your code goes here
int n = 5;
vector<pair<int, unordered_set<int>>> graph(n, make_pair(0, unordered_set<int>()));
graph[0].first = 1;
graph[1].second.insert(5);
graph[1].second.insert(6);
for (auto&& p : graph) {
std::cout << p.first << " " << p.second.size() << std::endl;
}
return 0;
}
```

Output (or run it here: https://ideone.com/kSVSnA):

```
1 0
0 2
0 0
0 0
0 0
```

Something else is wrong in some of the undefined behaviours and omitted bits in your code :)