Segmentation fault in C++ using vectors

Question

I'm having trouble with a segmentation fault caused by the following line:

heapVec[currentsize] = *(new Node(d));

What am I doing wrong here?

#include <vector>
using namespace std;

class Node {
private:
    int data;
public:
    Node(int);
    // ~Node();
};

class Heap {
private:
    vector<Node> heapVec;
    int currentsize;
public:
    Heap();
    // ~Heap();
    void insert(int);
    void extractMin();
    void reduceKey();
};

Node::Node(int d) {
    data = d;
}

void Heap::insert(int d) {
    heapVec[currentsize] = *(new Node(d));
    currentsize++;
}

Heap::Heap() {
    // this is the default constructor
    currentsize = 0;
}

int main() {
    Heap *h = new Heap;
    h->insert(10);
}

Solution 1

A vector doesn't grow automatically when you write out of its bounds using subscript operator. To insert to the end of the vector (increasing its size) use this:

heapVec.push_back(Node(d));

Also don't use *(new Node(d)), it won't segfault, but its a memory leak.

Solution 2

Before you access a vector by index you need to allocate space for it

 heapVec[currentsize] = *(new Node(d));

heapVec.resize(currentsize + 1) should do it. It will ensure that heapVec has at least currentsize + 1 elements and you can access currentsize.

One way to avoid this is by modifying your function. As you only are adding to the end of the vector.

void Heap::insert(int d) {
    heapVec.push_back( Node(d) );
    currentsize++;
}

Please note that you have vector<Node> and not vector<Node*> so you don't need the new call.

Also vector has a size() method so you don't need to duplicate it by having your own currentSize

Solution 3

First, you're writing outside the range of the vector, which is causing the segmentation fault. You need to either resize the vector to be large enough to contain it, or use push_back() to resize it for you.

Second, you have a memory leak - you're creating a Node with new for no good reason, then copying it into the vector, then losing the pointer and so never deleting the first object.

What you want is

heapVec.push_back(Node(d));

or in C++11

heapVec.emplace_back(d);

I would also get rid of your redundant currentsize variable and use heapVec.size() instead. Also, don't use new to create the local heap in main(); in general don't use new unless you really have to, and when you do, always use smart pointers or very carefully written code to make sure the object is deleted.