C ++ vector std :: bad_alloc ошибка
Я пытаюсь реализовать дерево суффиксов в 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 = ¤tNode[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)
Заранее спасибо.
Решение
Как отметил в комментарии Неманья Борич, вы перезаписываете свой стек, поэтому может произойти все что угодно. На моем ПК это случается bad_alloc в GCC, и простой сегфолт в лязг.
Посмотрите внимательно на эту строку:
currentNode = ¤tNode[currentNode->getFils().size() - 1];
currentNode это указатель на Node, В начале это указывает на переменную root, размещенные на стеке.
На первой итерации он меняется на ¤tNode[1 -1] что равно currentNode, Так что ничего не происходит (я полагаю, это не предназначено).
На следующей итерации он меняется на ¤tNode[2 - 1] что равно ¤tNode[1], что равно currentNode+1, Это адрес в стеке, сразу после root переменная. Это выделено, но это значение не Node*! Это может принадлежать int n;, но он может быть совершенно другим, основываясь на оптимизации компилятора.
В 3. итерации, когда вы пытаетесь использовать этот адрес в качестве Node экземпляры (которых нет), вы получаете неопределенное поведение, и с ними буквально может произойти все что угодно. Это может убить вашу кошку и сжечь ваш дом. Так что вам все еще везет, чтобы получить только bad_alloc,
Другие решения
Плохое выделение происходит из-за того, что стек / куча уже повреждены, поэтому ошибка должна произойти до того, как строка кода, на которую вы указали.
Ошибка случается когда count== suffixLen , Ниже приведен фрагмент кода из вашего кода, давайте предположим, что суффикс — это ab, поэтому суффикс суффикса равен 2.
После первого цикла счетчик равен 2, суффикс — это «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++;
}
Это очень неправильно.
currentNode = ¤tNode[currentNode->getFils().size() - 1];
Я предполагаю, что вы ожидаете переместить указатель currentNode к следующему элементу списка. Тем не менее, вы не распределили список. Вы инициализируете root как узел и затем указывает currentNode на root. За пределами root + sizeof (Node) нет выделенной памяти, которая фактически существует в стеке, но это не имеет значения, поскольку та же проблема возникла бы, если бы вы сделали новый Node ().
Я предполагаю, что вы думали, что root был своего рода вектором или предварительно распределенным списком, но я не могу быть уверен, каково ваше намерение. Первая итерация currentNode-> getFils (). Size () возвращает 1 и 1-1 = 0, поэтому currentNode устанавливает свой указатель на себя. На следующей итерации currentNode устанавливает себя в ячейку памяти на один размер (Node) за пределами root, которая находится на неизведанной территории.
Как отметил Неманья Борич, проблемная линия такова:
currentNode = ¤tNode[currentNode->getFils().size() - 1];
на каждой итерации вы вызываете конструктор копирования currentNode с адресом памяти в стеке, который увеличивается на каждом шаге (currentNode, currentNode + 1, currentNode + 2 и т. д.), делая это, вы портите Node.fils и, когда вы пытаетесь push_back элемент, вы получаете bad_alloc
С другой стороны, почему вам нужно увеличить ссылку на узел, если вы добавляете новые элементы в fils? Может быть, вы хотели работать со связанным списком?
У меня была та же проблема с использованием push_back (). Проблема заключается в том, что вектор должен иметь непрерывное пространство в вашей памяти для работы, и поскольку ваша ОС выделяет память во фрагментах, она может выделять пространство, которое может не вместить весь ваш вектор. Но если вы знаете окончательный размер вашего вектора, вы можете использовать std :: vector :: resize (), чтобы помочь вашей ОС выбрать лучшее место для размещения вашего вектора.
detector