Пытаясь закодировать Graph в c ++, иногда получая bad_alloc

Question

Я новичок в c ++ после изучения базового объектно-ориентированного программирования на Java, поэтому мне трудно понять, как освободить память.Назначение состояло в том, чтобы создать взвешенный ориентированный граф ...

Я получаю сообщение об ошибке: "завершается вызов после выброса экземпляра '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

Как уже упоминал ZE Nir, ваш код синтаксического анализа строки не может использовать любые входные данные, если в строке нет запятой ",".Конечно, вы можете отлаживать код анализа строк, так как отладка в любом случае является ценным навыком для разработки.

Однако возможная альтернатива отладке состоит в поиске существующей языковой конструкции C ++, которая делает то, что вы хотите сделать, иявляется частью языковой библиотеки, поэтому она уже отлажена.

Довольно часто вам нужно сделать " common stuff ", поэтому отладка кода вручную займет больше времени, чем поиск подходящегоранее существовавшая языковая конструкция, любезно предоставленная вашей любимой поисковой системой в Интернете и / или стекаперов.Возможность быстрого поиска языковой конструкции также является очень ценным умением.

В вашем случае функция 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.И полученный код легче понять для другого программиста.

Answer 2

Добро пожаловать в переполнение стека.Heads up: Извините за стиль, но вам действительно нужно научиться решать подобные проблемы самостоятельно.Это называется отладка.Я опытный программист, но мой код никогда не запускается так, как я думал, когда тестировал его в первый раз.Вам необходимо узнать, как использовать отладчик типа gdb или встроенный отладчик в среде Visual C++.

Теперь о вашем вопросе: следующий код получил переменную line со значением Hello,В line нет символа ,, следовательно, line = line.substr(commaPos + 1); возвращает 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.Да, и никогда не создавайте объекты в стеке.Я знаю, что некоторые места утверждают, что это нормально делать в функции main, но поверьте мне, это вызывает много проблем.