OneRaynyDay OneRaynyDay - 2 months ago 17
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.

Answer

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