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.