尝试在C ++中编码Graph，有时会获取bad_alloc [英] Trying to code Graph in c++, getting bad_alloc some of the time
问题描述
在学习了Java的基本面向对象程序设计后，我对c ++还是陌生的，因此我在处理内存释放方面遇到了困难.任务是创建一个加权有向图...
I'm new to c++ after learning basic Object Oriented Programming in Java so I'm having a difficult time grasping memory deallocation. The assignment was to create a Weighted Directed Graph...
我收到错误消息:在抛出'std :: bad_alloc'实例后调用终止当我通过代码运行某些输入时，what():std :: bad_alloc"，而且我很难弄清楚是什么原因造成的.
I'm getting the error: "terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc" when I run certain inputs through my code, and I'm having a difficult time figuring out what is causing it.
我搜索了该错误，发现这是一个内存问题，因此我尝试遍历代码并尝试查找任何泄漏，但是我不确定它们在哪里.大多数帖子都在谈论指针，我不倾向于实施指针，因为我不熟悉它们.谢谢您的时间！
I googled the error and found that it was a memory problem, so I attempted to go through my code and try to find any leaks, but I am not sure where they are. Most posts are talking about pointers, which I do not tend to implement because I am unfamiliar with them. Thank you for your time!
#include <iostream>
#include <fstream>
#include <string>
#include <array>
#include <iterator>
#include <map>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
class WDGraph {
private:
map<string,map<string,int>> edges;
vector<string> verts;
list<string> leaves;
list<string> roots;
list<string> selfEdges;
public:
list<string> getRoots() { return roots; }
list<string> getLeaves() { return leaves; }
void addVert(string key) {
verts.push_back(key);
}
void link(string start, string dest, int cost) {
edges[start].insert(make_pair(dest,cost));
if (!containsLeaf(dest) && !containsVert(dest))
leaves.push_back(dest);
if (!containsRoot(start) && !containsVert(start))
roots.push_back(start);
if (start == dest)
selfEdges.push_back(start);
roots.remove(dest);
leaves.remove(start);
}
bool containsVert(string key) {
for (int i=0; i < verts.size(); i++) {
if (key == verts[i]) {
return true;
}
}
return false;
}
bool containsRoot(string key) {
bool found = (find(roots.begin(), roots.end(), key) != roots.end());
return found;
}
bool containsLeaf(string key) {
bool found = (find(leaves.begin(), leaves.end(), key) != leaves.end());
return found;
}
WDGraph() { }
void printWDG() {
cout << "Printing Weighted Directed Graph." << endl;
for (auto itr1 = edges.begin(); itr1 != edges.end(); ++itr1) {
for (auto itr2 = itr1->second.begin(); itr2 != itr1->second.end(); ++itr2) {
if (itr2->first == "null" && containsRoot(itr1->first)) {
cout << "[" << itr1->first << "]";
}
else if (itr2->first != "null")
cout << "[" << itr1->first << " -> ";
cout << itr2->first << ", " << itr2->second << "] ";
}
cout << "" << endl;
}
}
void printNumVerts() {
cout << "Total number of vertices: " << verts.size() << endl;
}
void printRoots() {
int num_roots = 0;
cout << "Vertices with zero inbound edges: " << endl;
for (auto itr = roots.begin(); itr != roots.end(); ++itr) {
cout << "[" << *itr << "]" << endl;
num_roots++;
}
if (num_roots == 0) cout << "None" << endl;
}
void printLeaves() {
int num_leaves = 0;
cout << "Vertices with zero outbound edges:" << endl;
for (auto itr = leaves.begin(); itr != leaves.end(); ++itr) {
if (*itr != "null")
cout << "[" << *itr << "]" << endl;
num_leaves++;
}
if (num_leaves == 0) cout << "None" << endl;
}
void printSelfEdges() {
cout << "Vertices with self edges:" << endl;
for (auto itr = selfEdges.begin(); itr != selfEdges.end(); ++itr) {
cout << "[" << *itr << "]" << endl;
}
}
};
int main() {
WDGraph myWDG;
string filePath;
string line;
int weight;
size_t commaPos;
vector<string> sVector;
ifstream dataFile;
// cout << "Please enter the relative path to an input file." << endl;
// getline (cin, filePath);
// cout << "The file path you entered was " << filePath << endl;
// dataFile.open(filePath);
dataFile.open("input.csv"); //test input
while (getline (dataFile, line)) {
commaPos = line.find(',');
//Parse input file into string vector
while (line.length() >= 1) {
if (line.length() == 1) {
sVector.push_back(line);
break;
}
sVector.push_back(line.substr(0,commaPos));
line = line.substr(commaPos+1);
commaPos = line.find(',');
}
//Create vertices depending on number of parameters
if (sVector.size() == 1) {
if (!myWDG.containsVert(sVector[0])) {
myWDG.addVert(sVector[0]);\
}
myWDG.link(sVector[0], "null", 0);
}
if (sVector.size() == 3) {
if (!myWDG.containsVert(sVector[0])) {
myWDG.addVert(sVector[0]);
}
if (!myWDG.containsVert(sVector[1])) {
myWDG.addVert(sVector[1]);
}
weight = stoi(sVector[2]);
myWDG.link(sVector[0], sVector[1], weight);
}
sVector.clear();
}
myWDG.printWDG();
myWDG.printNumVerts();
myWDG.printRoots();
myWDG.printLeaves();
myWDG.printSelfEdges();
}
当我的.csv有简单的内容时，它可以按预期工作，例如:
When my .csv has simple stuff it works as expected, for example:
a,b,1
c,d,2
e
f,f,3
但是，如果我有类似的东西，则会在抛出'std :: bad_alloc'实例后收到错误终止调用:
However, if I have stuff like this I get the error "terminate called after throwing an instance of 'std::bad_alloc':
Hello
World,Hello,3
My,Name,4
Is
Nikki,Hello,3
推荐答案
如Z E Nir所述，如果行中没有逗号，则行解析代码将无法使用任何输入.当然，您可以调试行解析代码，因为无论如何调试都是一项宝贵的技能.
As mentioned by Z E Nir, your line parsing code fails to consume any input if there is no comma "," in the line. You can of course debug your line parsing code, as debugging is a valuable skill to develop anyway.
但是，调试的一种可能替代方法是找到一个现有的C ++语言构造，该构造可以执行您想要的操作，并且是语言库的一部分，因此已经调试完毕.
However, a possible alternative to debugging consists in finding an existing C++ language construct that does what you want to do, and is part of the language library so it is already debugged.
通常，您想要做的是"常见内容"，因此，根据您最喜欢的互联网搜索引擎和/或stackoverflow本身.能够快速找到语言结构也是一项非常有价值的技能.
Quite often, what you want to do is "common stuff", so debugging manual code will take more time than finding the appropriate pre-existing language construct, courtesy of your favorite internet search engine and/or stackoverflow itself. And being able to quickly find the language construct is also a very valuable skill.
在您的情况下，函数 getline()具有可选的定界符，默认情况下为换行符，但是您可以改为使用，"作为定界符，因此再次使用getline()，但是解析一行.它只需要一个假装为文件流的字符串对象，即std :: istringstream对象.
In your case, function getline() takes an optional delimiter, which is a newline by default, but you can instead have "," as delimiter and so use getline() again, but to parse a single line. It just takes a string object pretending to be a file stream, that is an std::istringstream object.
因此，您最终有两个嵌套循环，都使用getline():
So you end up with two nested loops, both using getline():
#include <sstream>
while (getline (dataFile, line)) {
std::istringstream iss{line};
std::string token;
while (getline (iss, token, ',')) {
std::cout << "DEBUG TOKEN LEN=" << token.length() << std::endl;
sVector.push_back(token);
}
// go build myWDG
}
这样，您就不必弄混一些细节，例如commaPos变量的值.这样产生的代码对于其他程序员来说更容易理解.
That way, you don't have to mess up with lowly details such as the value of your commaPos variable. And the resulting code is easier to understand for another programmer.
这篇关于尝试在C ++中编码Graph，有时会获取bad_alloc的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
