5

我试图在 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;
}

节点.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;
}

节点.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

生成文件

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)

提前致谢。

4

5 回答 5

7

正如 Nemanja Boric 在评论中指出的那样，你正在覆盖你的堆栈，所以任何事情都可能发生。在我的 PC 上，它恰好bad_alloc在 GCC 中，并且在 clang 中是普通的段错误。

仔细看这条线：

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

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

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

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

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

于 2013-11-22T20:28:29.683 回答
1

发生错误分配是因为堆栈/堆已经损坏，因此错误应该发生在您指出的代码行之前。

错误发生在count== suffixLen . 下面是您的代码中的代码片段，假设“suffix”是“ab”，那么“suffixLen”是 2。

第一次循环后，count为2，'suffix'为'b'，在第二次循环中，代码

suffix = suffix.substr(1,suffixLen);

将失败并导致内存问题，因为 1 超出范围。所以你应该处理“后缀”中只剩下一个字符的情况

  suffixLen = suffix.length();
    count = 1;
    currentNode = &root;

    while(count <= suffixLen){


        // bad_alloc occurs here
        (*currentNode).addFils(Node(suffix[0], vector<Node>(), i));


        suffix = suffix.substr(1,suffixLen);
        count++;
    }
于 2013-11-22T20:30:00.223 回答
1

这是非常错误的。

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

我的猜测是您希望将 currentNode 指针移动到列表的下一个元素。但是，您尚未分配列表。您将 root 初始化为 Node，然后将 currentNode 指向 root。除了 root+sizeof(Node) 之外没有分配的内存，它实际上存在于堆栈上，但这无关紧要，因为如果你执行了 new Node()，也会出现同样的问题。

我假设您认为 root 是某种向量或预分配列表，但我无法确定您的意图是什么。第一次迭代 currentNode->getFils().size() 返回 1 和 1-1 = 0，因此 currentNode 将其指针设置为自身。下一次迭代，currentNode 将自己设置为超出 root 的一个 sizeof(Node) 的内存位置，该位置处于未知领域。

于 2013-11-22T20:34:49.080 回答
1

正如 Nemanja Boric 指出的那样，有问题的行是：

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

在每次迭代中，您都在调用 currentNode 的复制构造函数，堆栈中的内存地址在每一步都会增加（currentNode、currentNode + 1、currentNode + 2 等），通过这样做，您正在破坏Node.fils，当您尝试push_back 一个元素，你得到bad_alloc

另一方面，如果要添加新元素，为什么需要增加对节点的引用fils？可能是您想使用链表吗？

于 2013-11-22T20:36:27.713 回答
0

我在使用 push_back() 时遇到了同样的问题。问题是向量需要在您的内存上有一个连续的空间才能工作，并且由于您的操作系统在片段中分配内存，它可能会分配一个可能无法包含所有向量的空间。但是，如果您知道向量的最终大小，则可以使用 std::vector::resize() 来帮助您操作系统选择分配向量的最佳位置。

于 2016-05-02T13:49:44.410 回答