C++ 向量 std::bad_alloc 错误 [英] C++ vector std::bad_alloc error

问题描述

我正在尝试用 C++ 实现一个后缀树在向我的向量列表添加节点时，它在向树中添加第三个元素后抛出 std::bad_alloc .我不知道为什么它在第三次之后发生，你能帮我解决这个 bad_alloc 错误吗?

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 ?

这是我的代码:

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)

提前致谢.

推荐答案

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

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.

仔细看这条线:

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

currentNode 是指向 Node 的指针.一开始，它指向变量root，分配在栈上.

currentNode is pointer to Node. At the beginning, it points to variable root, allocated on stack.

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

In the first iteration, it changes to &currentNode[1 -1] which equals to currentNode. So nothing happens (this isn't intended I suppose).

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

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.

在 3. 迭代中，当您尝试将此地址用作 Node 实例(不是)时，您会得到未定义的行为，并且实际上任何事情都可能发生.它可以杀死你的猫并烧毁你的房子.所以你仍然很幸运，只得到 bad_alloc.

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.

这篇关于C++ 向量 std::bad_alloc 错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！