5

ベクトル リストにノードを追加するときに、C++ でサフィックス ツリーを実装しようとしています。ツリーに 3 番目の要素を追加した後、std::bad_alloc がスローされます。3 回目以降に発生する理由がわかりません。この 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;
}

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

メイクファイル

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_allocGCCにあり、clangに単純なセグメンテーションがあります。

この行をよく見てください。

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

currentNodeへのポインタNodeです。root最初は、スタックに割り当てられたvariable を指します。

最初の反復では、&currentNode[1 -1]which が に変更されcurrentNodeます。したがって、何も起こりません (これは意図したものではないと思います)。

次の反復では、 に等しい 、 に&currentNode[2 - 1]等しい に変更されます。これは、変数の直後のスタック上のアドレスです。割り当てられていますが、その値は!ではありません。に属している可能性がありますが、コンパイラの最適化に基づいて、完全に異なる場合があります。&currentNode[1]currentNode+1rootNode*int n;

3. 反復では、このアドレスをインスタンスとして使用しようとするとNode(そうではありません)、未定義の動作が発生し、文字通り何でも起こります。それはあなたの猫を殺し、あなたの家を燃やすことができます. だからあなたはまだ幸運ですbad_alloc.

于 2013-11-22T20:28:29.683 に答える
1

これは非常に間違っています。

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

私の推測では、 currentNode ポインターをリストの次の要素に移動することを期待しています。ただし、リストを割り当てていません。root を Node として初期化し、currentNode を root にポイントします。実際にはスタック上に存在する root+sizeof(Node) を超えて割り当てられたメモリはありませんが、new Node() を実行した場合に同じ問題が発生するため、これは関係ありません。

ルートはある種のベクターまたは事前割り当てリストだと思っていたと思いますが、あなたの意図が何であったかはわかりません。最初の反復である currentNode->getFils().size() は 1 と 1-1 = 0 を返すため、currentNode はそのポインターをそれ自体に設定します。次の反復である currentNode は、未知の領域にある root の 1 sizeof(Node) 先のメモリ位置に自身を設定します。

于 2013-11-22T20:34:49.080 に答える
1

スタック/ヒープがすでに破損しているため、不正な割り当てが発生するため、指摘したコードの行の前にエラーが発生するはずです。

のときにエラーが発生しcount== suffixLen ます。以下はコードのコード スニペットです。「suffix」が「ab」で、「suffixLen」が 2 であると仮定しましょう。

最初のループの後、count は 2、'suffix' は 'b'、2 番目のループで、コード

suffix = suffix.substr(1,suffixLen);

1 が範囲外であるため、失敗してメモリの問題が発生します。したがって、「接尾辞」に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

Nemanja Boric が指摘したように、問題のある行は次のとおりです。

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

繰り返しごとに、スタック内のメモリアドレスがステップごとに増加する（currentNode、currentNode + 1、currentNode + 2など）を使用してcurrentNodeのコピーコンストラクターを呼び出しています。これを行うと、破損Node.filsし、試してみると要素を push_back するには、bad_alloc

一方、新しい要素を に追加する場合、ノードへの参照を増やす必要があるのはなぜfilsですか? リンクされたリストを操作したかったのかもしれません。

于 2013-11-22T20:36:27.713 に答える
0

push_back() を使用して同じ問題が発生しました。問題は、ベクターが機能するためにメモリ上に連続したスペースが必要であり、OS がフラグメントでメモリを割り当てるため、すべてのベクターを含めることができないスペースを割り当てる可能性があることです。ただし、ベクトルの最終的なサイズがわかっている場合は、 std::vector::resize() を使用して、OS がベクトルを割り当てる最適な場所を選択できるようにすることができます。

于 2016-05-02T13:49:44.410 に答える