尝试用 C++ 编写 Graph，有时会得到 bad_alloc

Question

我在 Java 中学习了基本的面向对象编程后才开始接触 c++，所以我很难掌握内存释放。作业是创建一个加权有向图...

我收到错误：“在抛出 'std::bad_alloc' 的实例后调用终止 what(): std::bad_alloc" 当我运行通过我的代码进行某些输入时，我很难弄清楚是什么原因造成的。

我用谷歌搜索了这个错误，发现这是一个内存问题，所以我试图检查我的代码并试图找到任何泄漏，但我不确定它们在哪里。大多数帖子都在谈论指针，我不倾向于实现它们，因为我不熟悉它们。感谢您的宝贵时间！

#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 包含简单内容时，它会按预期工作，例如：

a,b,1
c,d,2
e
f,f,3

但是，如果我有这样的东西，我会收到错误消息“在抛出 'std::bad_alloc' 的实例后调用终止：

Hello
World,Hello,3
My,Name,4
Is
Nikki,Hello,3

Answer 1

欢迎来到 Stack Overflow。注意：对这种风格感到抱歉，但你真的必须学会自己解决这类问题。这叫做调试。我是一位经验丰富的程序员，但我的代码从未运行完全像我第一次测试时所想的那样。您需要学习如何使用 gdb 之类的调试器或 Visual C++ 环境中的内置调试器。

现在关于你的问题：以下代码接收了值为 Hello 的变量 line。 line 中没有 , 字符，因此 line = line.substr(commaPos + 1); return Hello 始终存在，并且由于 'Hello' 字符串包含一个以上的字符，您陷入无限循环。

//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(',');
        }

问题不止于此。由于无限循环的每次迭代你的程序执行：sVector.push_back(line.substr(0, commaPos)); 你实际上分配了越来越多的内存，直到你的系统不再给这个过程。这就是您获得 bad_alloc 异常的地方。换句话说，你的错误不是关于C++，而是关于糟糕的编程。

重新考虑您的程序，并考虑您希望如何像 Hello 一样处理 edge-cases。哦，永远不要在堆栈上构建对象。我知道有些地方声称可以在 main 函数中执行此操作，但相信我这会造成很多麻烦。

Answer 2

如 Z E Nir 所述，如果行中没有逗号“,”，您的行解析代码将无法使用任何输入。您当然可以调试您的行解析代码，因为无论如何调试都是一项宝贵的开发技能。

但是，调试的一种可能替代方法是找到一个现有的 C++ 语言构造，它可以执行您想要执行的操作，并且是语言库的一部分，因此它已经过调试。

很多时候，您想做的是“常见的东西”，因此调试手动代码比找到合适的 pre-existing 语言结构要花费更多时间，礼貌你最喜欢的互联网搜索引擎 and/or Whosebug 本身。而能够快速找到语言结构也是一项非常宝贵的技能。

在你的例子中，函数 getline() 接受一个可选的分隔符，默认情况下它是一个换行符，但你可以改为使用“，”作为分隔符，因此使用 getline( ) 再次，但解析单行。它只需要一个字符串对象伪装成一个文件流，即一个 std::istringstream 对象。

所以你最终得到两个嵌套循环，都使用 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 变量值之类的低级细节。并且生成的代码对于其他程序员来说更容易理解。

尝试用 C++ 编写 Graph，有时会得到 bad_alloc

Trying to code Graph in c++, getting bad_alloc some of the time

c++

csv

memory

allocation

bad-alloc