vector std::bad_alloc

Shal (1)
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 have no idea why it happens after the third time, Could you help me resolving this error ?
Here's my code :

suffix_tree.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
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.
Last edited on
Cubbi (4774)
1
2
3
4
5
 
       Node root = Node();
...
       currentNode = &root;
...
       currentNode = &currentNode[currentNode->getFils().size() - 1];

When you evaluate currentNode[N], you're attempting to access Nth member of an array whose first element is pointed to by the pointer currentNode.. but it is not pointing at an element of any array.

it throws std::bad_alloc after adding a third element into the tree

The first time around, your currentNode->getFils().size() - 1 is zero, so you just reset it back to the same root object, the second time around you move it to uninitialized memory, and third time around you try to access it (undefined behavior then takes place, which just happened to result in a bad_alloc for you - was a segfault for me)
Last edited on
Topic archived. No new replies allowed.