C++ vector std::bad_alloc error

Question

I'm trying to implement a suffix tree in c++ while adding nodes to my vector list, it throws std::bad_alloc after adding a third element into the tree. I don't know why it occurs after the third time, Could you help me resolving this bad_alloc error ?

Here's my code :

suffix_tree.cpp

#include <iostream>
#include <fstream>
#include <cmath>
#include <sstream>
#include <string>
#include <cstring>
#include "node.h"

using namespace std;

Node build_suffix_tree(string text){
    Node root = Node();
    int n = text.length();
    int count;
    Node * currentNode = &root;
    Node tmpNode;
    string suffix;
    int suffixLen;


    for(int i=0; i<n; i++){
        suffix = text.substr(i,n);
        suffixLen = suffix.length();
        count = 1;
        currentNode = &root;

        while(count <= suffixLen){
            cout << suffix << endl;
            int pos = -1;


            // bad_alloc occurs here
            (*currentNode).addFils(Node(suffix[0], vector<Node>(), i));


            cout << currentNode->getFils().size() << endl;
            currentNode = &currentNode[currentNode->getFils().size() - 1];

            suffix = suffix.substr(1,suffixLen);
            count++;
        }
        cout << "  " << endl;
    }
    return root;
}


int main(){
   string text = "helloeveryone";
   Node root = build_suffix_tree(text);
   return 0;
}

node.cpp

#include <string>
#include <vector>
#include "node.h"

using namespace std;

Node::Node(){
    c = ' ';
    fils = vector<Node>();
    pos = -1;
}

Node::Node(char t, vector<Node> l, int p){
    c = t;
    fils = l;
    pos = p;
}

void Node::addFils(Node n){
    fils.push_back(n);
}

char Node::getString(void){
    return c;
}

vector<Node> Node::getFils(){
    return fils;
}

void Node::setFils(vector<Node> l){
    fils = l;
}

node.h

#include <string>
#include <vector>

#ifndef NODE_H
#define NODE_H

class Node
{
public:
    char c;
    std::vector<Node> fils;
    int pos;
    Node();
    Node(char c, std::vector<Node> fils, int p);
    void addFils(Node n);
    char getString(void);
    std::vector<Node> getFils();
    void setFils(std::vector<Node>);
};

#endif // NODE_H

Makefile

CC=g++
CFLAGS= -g
LDFLAGS=
EXEC=suffix_tree

all: $(EXEC)

suffix_tree: suffix_tree.o node.o
$(CC) -o suffix_tree suffix_tree.o node.o $(LDFLAGS)

node.o: node.cpp
$(CC) -o node.o -c node.cpp $(CFLAGS)

suffix_tree.o: suffix_tree.cpp node.h
$(CC) -o suffix_tree.o -c suffix_tree.cpp $(CFLAGS)

clean:
rm -rf *.o

mrproper: clean
rm -rf $(EXEC)

Thanks in advance.

Answer 1

As Nemanja Boric pointed out in the comment, you're overwriting your stack, so anything can happen. On my PC, it happens to be bad_alloc in GCC, and plain segfault in clang.

Look closely on this line:

currentNode = &currentNode[currentNode->getFils().size() - 1];

currentNode is pointer to Node. At the beginning, it points to variable root, allocated on stack.

In the first iteration, it changes to &currentNode[1 -1] which equals to currentNode. So nothing happens (this isn't intended I suppose).

In the next iteration it changes to &currentNode[2 - 1] which equals to &currentNode[1], which equals to currentNode+1. That is an address on the stack, right after the root variable. It's allocated, but it's value is not a Node*! It can belong to int n;, but it may be completely different, base on compiler optimizations.

In the 3. iteration, when you try to use this address as a Node instance (which is not), you get undefined behavior and them literally anything can happen. It can kill your cat and burn your house. So you're still lucky, to get only bad_alloc.

Answer 2

Bad alloc happens because the stack/heap is already damaged, so the error should happens before the line of the code you pointed it out.

The error happen when count== suffixLen . The below is the code snippet from your code, let's assume 'suffix' is 'ab', so 'suffixLen' is 2.

After the first loop, count is 2, 'suffix' is 'b', at the second loop, the code

suffix = suffix.substr(1,suffixLen);

will fail and cause memory problems because 1 is out of the range. So you should deal with case when only one char left in 'suffix'

  suffixLen = suffix.length();
    count = 1;
    currentNode = &root;

    while(count <= suffixLen){


        // bad_alloc occurs here
        (*currentNode).addFils(Node(suffix[0], vector<Node>(), i));


        suffix = suffix.substr(1,suffixLen);
        count++;
    }

Answer 3

This is very wrong.

currentNode = &currentNode[currentNode->getFils().size() - 1];

My guess is that you are expecting to move currentNode pointer to the next element of a list. However, you have not allocated a list. You initialize root as a Node and then point currentNode to root. There is no allocated memory beyond root+sizeof(Node), which actually exists on the stack but that's irrelevant as the same problem would have occured if you had done new Node().

I assume you thought root was some sort of vector or preallocated list but I can't be certain what your intent was. The first iteration, currentNode->getFils().size() returns 1 and 1-1 = 0, so, currentNode sets its pointer to itself. The next iteration, currentNode sets itself to the memory location one sizeof(Node) beyond root which is in uncharted territory.

Answer 4

As Nemanja Boric pointed out, problematic line is:

currentNode = &currentNode[currentNode->getFils().size() - 1];

on every iteration, you're calling currentNode's copy constructor with a memory address in the stack that increases on every step (currentNode, currentNode + 1, currentNode + 2, etc), by doing this, you're corrupting Node.fils and, when you try to push_back an element, you get the bad_alloc

On the other hand, why you need to increase the reference to the node if you're adding new elements to fils? May it be that you wanted to work with a linked list?

Answer 5

I had the same problem using push_back(). The issue is that vector need to have a continuous space on your memory to work and since your OS allocate memory in fragment it might allocate a space that may not be able to contain your all vector. But if you know the final size of your vector, you can use std::vector::resize() to help you OS choose a best place to allocate your vector.