C ++向量std :: bad_alloc错误

Question

我正在尝试在c ++中实现后缀树，同时将节点添加到向量列表中，在向树中添加第三个元素后，它会引发std :: bad_alloc。我不知道为什么它在第三次之后发生，您能帮我解决这个bad_alloc错误吗？

这是我的代码：

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;
}

节点

#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

生成文件

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)

提前致谢。

Answer 1

正如Nemanja Boric在评论中指出的那样，您正在覆盖堆栈，因此任何事情都可能发生。在我的PC上，它恰好bad_alloc在GCC中，而普通的segfault在clang中。

仔细观察这一行：

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

currentNode是的指针Node。首先，它指向root在栈上分配的variable 。

在第一次迭代中，它更改为&currentNode[1 -1]等于currentNode。所以什么也没发生（我想这不是故意的）。

在下一次迭代中，它更改为&currentNode[2 - 1]等于&currentNode[1]，等于currentNode+1。那是堆栈上的地址，紧随root变量之后。它已分配，但其值不是Node*！它可以属于int n;，但基于编译器优化可能完全不同。

在3.迭代中，当您尝试使用该地址作为Node实例（不是）时，会得到未定义的行为，并且它们实际上可能会发生。它会杀死猫并烧毁房屋。因此，您仍然很幸运，只能得到bad_alloc。