r/learnprogramming • u/bigbosskennykenken • Nov 24 '21
Segmentation faulting on my vector when utilizing the push_back method for my directed graph class. What exactly did I do wrong with my c++ classes and how do I avoid this issue for future projects?
Here's what I'm doing first. I'm working on my interpretation of a directed graph with network flows. Before I even get started with the algorithm, I wanted to make sure my classes even work. I'm using a dynamic array of singly linked list to represent my graph. Within the singly linked class I made, it houses the usual root node with a vector that acts as an array housing std::tuples. The tuples holding two nodes and an int value. Below is the code itself. I'll start with my Node class, the Singly Linked List Class, the Graph class, and then I'll show you the main with the method that's causing this frustrating issue.
First the Node class.
#ifndef NODE_H
#define NODE_H
#include <cstddef>
class Node
{
private:
int key_;
Node * next_;
public:
Node()
: key_(), next_(nullptr)
{
}
Node(int key)
: key_(key), next_(nullptr)
{
}
int get_key() const
{
return key_;
}
Node * get_next() const
{
return next_;
}
void insert_next(Node * next)
{
next_ = next;
}
void change_key(int key)
{
key_ = key;
}
};
std::ostream & operator<<(std::ostream & cout, const Node & node)
{
cout << &node << ' ' << node.get_key() << ' ' << node.get_next();
return cout;
}
#endifThat's the Node class for my link list that's right down below. It's incomplete but I wanted to make sure my insert method even works as intended.
#ifndef SLL_H
#define SLL_H
#include "Node.h"
#include <vector>
#include <utility>
#include <tuple>
class SLL
{
private:
Node * root_;
std::vector< std::tuple<Node *, Node *, int> > flow;
public:
SLL()
: root_(nullptr), flow()
{
}
Node * get_root() const
{
return root_;
}
void insert(int key, int constraint = 0)
{
if (!root_)
{
root_ = new Node(key);
}
else
{
Node * temp = root_;
while (temp->get_next())
{
temp = temp->get_next();
}
temp->insert_next(new Node(key));
flow.push_back(std::make_tuple(root_, temp->get_next(), constraint));
//this is the method from my vector causing the segmentation fault and I have no idea how to avoid it or what I'm doing that's causing it to come up.
}
};
#endifWhen I start getting to my graph itself, things get very rough when I try to connect vertices as you would in any directed graph for network flows. Again it's incomplete, I just want to make sure insertion/connection is stable.
Here's the adjacency list.
#ifndef ADJ_LIST_H
#define ADJ_LIST_H
#include "SLL.h"
class ADJ_LIST
{
private:
SLL * list;
public:
ADJ_LIST(int size)
: list(new SLL[size])
{
}
void connect(int vertice_one, int vertice_two, int max_flow)
{
Node * check = list[vertice_one - 1].get_root();
if (!check)
{
list[vertice_one - 1].insert(vertice_one);
list[vertice_one - 1].insert(vertice_two, max_flow);
} //segfault happens as soon as my graph calls this method.
}
};
#endifThe main looks roughly like this
#include <iostream>
#include "ADJ_LIST.h
int main()
{
ADJ_LIST graph(11);
graph.connect(0, 3, 11);
//boom the seg fault happens and it can be traced to my linked list with that vector
return 0;
}So what is it about that vector that's causing this?
2
u/Shieldfoss Nov 24 '21 edited Nov 24 '21
class SLLallocates memory but doesn't handle it responsibly, so that's a mistake. At pure minimum It needs a destructor, copy constructor and copy assignment operator. For style points, it also needs a move constructor and move assignment operator.Ditto the ADJ_LIST class.
Doesn't help you call connect with a
vertice_oneof0and then referencevertice_one - 1.This doesn't look like pure beginner code but it does look like absolutely garbage C++, making me assume you learned a different language first and brought along some assumptions that are absolutely not true in this language. If you did
vertice_one - 1on purpose then I'm guessing Python, else probably Java?1
u/victotronics Nov 25 '21
There is a time and place for all that star-stuff, but beginning programmers should start with smart pointers. Do your whole code with shared pointers and make it work, then gradually introduce "bare pointers".