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

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)

提前致谢。

- guillaume guerin

---

这个问题具体是什么？ - cm2

这行代码有问题。 - Nemanja Boric

我也在想，由于向量重新分配，currentNode指针是否会变得悬空？不过不确定。 - user2672165

@user2672165 悬空指针通常不会导致 std::bad_alloc，虽然... - twalberg

Answer 1

正如Nemanja Boric在评论中指出的，您正在覆盖堆栈，因此可能会发生任何事情。 在我的电脑上，GCC会发生bad_alloc，而clang则会产生普通的segfault。

请仔细查看这一行：

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

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

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

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

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

- v154c1

Answer 2

Bad alloc发生的原因是堆栈已经损坏，因此错误应该在你指出的代码行之前发生。当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++;
    }

- Matt

---

如果我正确理解标准的话（在N3690中是21.4.7.8 [string::substr]），它要求substr的第一个参数必须小于或等于size()。因此，在长度为1个字符的字符串的情况下，调用substr(1)应该是有效的。对于空字符串，它应该抛出异常而不是崩溃。 - v154c1

Answer 3

这是非常错误的。

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

我猜你是想将currentNode指针移动到列表的下一个元素。然而，你没有分配列表。你将root初始化为一个节点，然后将currentNode指向root。除了root+sizeof(Node)在堆栈上存在，但这并不重要，因为如果你使用new Node()，同样的问题也会发生，因为没有超过root+sizeof(Node)的分配的内存。

我假设你认为root是某种向量或预分配列表，但我不能确定你的意图是什么。第一次迭代，currentNode->getFils().size()返回1，1-1=0，所以currentNode将其指针设置为自己。下一次迭代，currentNode将自己设置为root之外一个sizeof(Node)的内存位置，这是未知领域。

- doog abides

Answer 4

作为Nemanja Boric指出的，有问题的行是：

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

在每次迭代中，您都会使用堆栈中逐步增加的内存地址（currentNode、currentNode + 1、currentNode + 2等）调用currentNode的复制构造函数，通过这样做，您正在破坏Node.fils，当您尝试推入元素时，会出现bad_alloc。

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

- jcm

Answer 5

我曾经使用push_back()遇到过同样的问题。问题在于，向量需要在内存中具有连续的空间才能工作，由于操作系统分配的内存是碎片化的，它可能分配一个无法容纳您所有向量的空间。但是，如果您知道向量的最终大小，可以使用std::vector::resize()来帮助您的操作系统选择最佳的位置来分配向量。

- The game