Implementing a Suffix Trie using OOP/C++

Question

I am trying to implement a suffix trie in C++ for a programming assignment. Now I think I have the right idea, but I keep getting a segmentation fault and I haven't been able to find what's causing it.

For this assignment, we are encouraged to use VIM/some other basic text editor, and compile programs from the console. Nevertheless, I've downloaded CLion to try and debug the code so I can find the error.

Now when running in CLion I get the message

terminate called after throwing an instance of 'std::bad_alloc'
   what():  std::bad_alloc

Trying to run the debugger gives the message

Error during pretty printers setup: 
Undefined info command: "pretty-printer".  Try "help info".
Some features and performance optimizations will not be available.

I'm new to CLion and I'm not sure what to do about this (The only JetBrains IDE I use is Pycharm). Can you help me resolve this?

Now the program itself consists of three classes, Trie, Edge and Node, whose implementations can be seen below. The main idea behind the implementation of the Trie is in the constructor of Trie.cpp.

The code is detailed in full below. I appreciate any help.

---

Main.cpp

#include <iostream>
using namespace std;

#include "Trie.hpp"

int main(){

    string s = "Stef";
    Trie trie(s);   


    return 0;
}

Trie.hpp

#ifndef TRIE_HPP
#define TRIE_HPP

#include <string>
#include "Node.hpp"
#include "Edge.hpp"
using namespace std;

class Trie{

    private:
        string T;
        vector<Node> nodes;
        void addWord(Node*, string);

    public:
        Trie(string);       

};

#endif

Trie.cpp

#include <iostream>
#include <cstring>
#include "Trie.hpp"
using namespace std;

Trie::Trie(string T){   
    T += "#";                           //terminating character     
    this->T = T;

    vector<string> suffix;              //array of suffixes
    for(unsigned int i = 0; i < T.length(); i++)
        suffix.push_back(T.substr(i, T.length()-i));

    //Create the Root, and start from it
    nodes.push_back(Node(""));          //root has blank label
    Node* currentNode = &nodes[0];

    //While there are words in the array of suffixes
    while(!suffix.empty()){

        //If the character under consideration already has an edge, then this will be its index. Otherwise, it's -1.
        int edgeIndex = currentNode->childLoc(suffix[0].at(0));     

        //If there is no such edge, add the rest of the word
        if(edgeIndex == -1){
            addWord(currentNode, suffix[0]);                //add rest of word
            suffix.erase(suffix.begin());                   //erase the suffix from the suffix array
            break;                                          //break from the for loop
        }

        //if there is
        else{
            currentNode = (currentNode->getEdge(edgeIndex))->getTo();       //current Node is the next Node
            suffix[0] = suffix[0].substr(1, suffix[0].length());                        //remove first character
        }           
    }   
}

//This function adds the rest of a word
void Trie::addWord(Node* parent, string word){  
    for(unsigned int i = 0; i < word.length(); i++){                //For each remaining letter
        nodes.push_back(Node(parent->getLabel()+word.at(i)));       //Add a node with label of parent + label of edge
        Edge e(word.at(i), parent, &nodes.back());                  //Create an edge joining the parent to the node we just added
        parent->addEdge(e);                                         //Join the two with this edge   
    }
}

Node.hpp

#ifndef NODE_HPP
#define NODE_HPP

#include <string>
#include <vector>
#include "Edge.hpp"
using namespace std;

class Node{

    private:
        string label;           
        vector<Edge> outgoing_edges;

    public:
        Node(); 
        Node(string);   
        string getLabel();  
        int childLoc(char);
        void addEdge(Edge);
        Edge* getEdge(int);
};

#endif

Node.cpp

#include "Node.hpp"
using namespace std;

Node::Node(){
}

Node::Node(string label){
    this->label = label;
}

string Node::getLabel(){
    return label;
}

//This function returns the edge matching the given label, returning -1 if there is no such edge. 
int Node::childLoc(char label){
    int loc = -1;
    for(unsigned int i = 0; i < outgoing_edges.size(); i++)
        if(outgoing_edges[i].getLabel() == label) 
            loc = i;
    return loc;
}

void Node::addEdge(Edge e){
    outgoing_edges.push_back(e);
}

Edge* Node::getEdge(int n){
    return &outgoing_edges[n];
}

Edge.hpp

#ifndef EDGE_HPP
#define EDGE_HPP

#include <string>
using namespace std;

class Node;         //Forward definition

class Edge{

    private:
        char label;
        Node* from;
        Node* to;

    public:
        Edge(char, Node*, Node*);
        char getLabel();
        Node* getTo();
        Node* getFrom();    
};

#endif

Edge.cpp

#include "Edge.hpp"
using namespace std;

Edge::Edge(char label, Node* from, Node* to){
    this->label = label;
    this->from = from;
    this->to = to;
}

char Edge::getLabel(){
    return label;
}

Node* Edge::getFrom(){
    return from;
}

Node* Edge::getTo(){
    return to;
}

Answer 1

&nodes[0];, &nodes.back() - you're storing pointers into a vector for later use, and these become invalid when the vector's underlying storage is relocated as you add elements to it.

Read about pointers in general, and dynamic allocation in particular, in your favourite C++ book.
If you don't yet have a favourite C++ book, pick one from this list.