OneRaynyDay - 1 year ago 84
C++ Question

vector<pair<int, unordered_set<int>>> gives segmentation fault when supplying default constructor argument for pair

** 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. **

The code that doesn't work

``````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)`
, it throws a segfault, but I'm not 100% sure why it's happening.

The code that does work

``````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)`
. It was my boolean array that was causing issues. Sorry for the confusion! I have flagged this post to be deleted by the mods.

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 I tried to use some print statements to see where the segfault was happening. It was on the line after and I'm guessing the buffer to stdout was not flushed when segfault occured so for the line before it also did not display the print. I won't be using print for binary-searching my bugs for segfaults anymore - learned a valuable lesson here.

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() {
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 :)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download