EXC_BAD_ACCESS, calling getter

Question

I'm not very good with memory management and I'm hoping someone can help explain to me why I am getting the EXC_BAD_ACCESS (code=1...) error. Xcode says that the error occurs when calling the getWord() method.

I am implementing a trie data structure and the error occurs when I try to get a word from my node. I think the problem is with my add or addPhrase method but I cant figure out whats going on. Any suggestions are appreciated.

Trie and Node Class:

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <sstream>


using namespace std;


class Node
{
private:
    string word;
    bool endOfSentence = false;
    int weight = -1;


public:

    vector<Node> children = {};

    Node() {
        this->setWord("");
    }

    Node(string s){
        this->setWord(s);
    }

    string getWord(){
        return this->word;
    }
    /*vector<Node> getChildren() {   //children private
        return this->children;
    }*/
    void setWord(string s) {
        this->word = s;
    }

    void setEOS(){
        this->endOfSentence = true;
    }

    void setWeight(int weight){
        this->weight = weight;
    }
};


class Trie
{
public:
    Node root = *new Node();

    string get(string p) {
        string s = "stub";
        return s;
    }

    void add(vector<string> phrase, int weight){
        Node current = this->root;
        vector<string> sentence = phrase;
        int w = weight;
        int found = -1;

        for (int i = 0; i < current.children.size(); i++) {
            if (phrase[0] == current.children[i].getWord()) {
                found = i;
            }
        }
        if (found >= 0) {
            current = current.children[found];
            sentence.erase(sentence.begin());
            add(sentence,w);
        }
        else {
            addPhrase(sentence,w);
        }
    }

    void addPhrase(vector<string> phrase, int weight) {
        Node current = this->root;
        for (int i = 0; i < phrase.size(); i++) {
            Node temp = *new Node(phrase[i]);
            current.children.push_back(temp);
            current = current.children[current.children.size() - 1];
            if (i == phrase.size() - 1) {
                current.setEOS();
                current.setWeight(weight);
            }
        }
    }
};

Main - just attempts to the the word from the first node.

#include "Trie.cpp"
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
    // Initialize trie up here
    Trie myTrie = *new Trie();

    // parse input lines until I find newline
    for(string line; getline(cin, line) && line.compare(""); ) {
        stringstream ss(line);
        string string_weight;
        ss >> string_weight;
        int weight = stoi(string_weight);

        // I am just going to put these words into a vector
        // you probably want to put them in your trie

        vector<string> phrase = {};
        for(string word; ss >> word;) {
            phrase.push_back(word);
        }


        myTrie.add(phrase, weight);


    }
    // parse query line
    string query;
    getline(cin, query);

    cout << myTrie.root.children[0].getWord() << endl;



    return 0;
}

Answer 1

Do you have some experience with Java, by chance? In any case, there are a couple of important things to note about C++: a simple assignment or initialization does not link a variable as a reference to an existing object, and the keyword new is not needed to create new objects.

Node current = this->root;

This line, in both add and addPhrase, creates a Node object which is a copy of your root node (children and all). So anything you do to current won't affect root. And at the very end of main, the line

cout << myTrie.root.children[0].getWord() << endl;

is invalid because myTrie.root.children is still empty, possibly causing your crash (unless I missed an earlier problem).

The new keyword in C++ creates an object with dynamic storage duration instead of the usual automatic storage duration, which means that the object will not be destroyed for any reason unless you use the delete keyword on a pointer to that object. So any time you do something like

Trie myTrie = *new Trie();

the program creates a Trie object without a name because of the new, then creates the myTrie object by copying from that object, but the first object will exist for the rest of the program and is considered "leaked". Too many leaks, besides being bad form, will increase your program's usage of computer memory in a way that can't be reversed until the program stops. To default-construct a Trie object, it's enough to just write:

Trie myTrie;

In add and addPhrase, you want your variable current to relate to different existing Node objects, not to be an independent Node that lives for the duration of the function. This is actually a use case for a raw pointer:

void addPhrase(vector<string> phrase, int weight) {
    Node* current = &this->root;
    for (int i = 0; i < phrase.size(); i++) {
        Node temp(phrase[i]);
        current->children.push_back(temp);
        current = &current->children.back();
        if (i == phrase.size() - 1) {
            current->setEOS();
            current->setWeight(weight);
        }
    }
}

(Note current->children.back() is a shorter way of saying current->children[current->children.size()-1].)