Mergesort - std :: bad_alloc geworfen beim Versuch, Vektor zuzuweisen

Question

Guten Tag, Damen und Herren. Es ist also nicht mein Tag für Fehler. Implementieren von Mergesort (nicht in Platzierung) in C ++, und ich habe echte Probleme mit dem Code, ohne eine Ahnung warum. Die zweitletzte Linie der mergeSort() Funktion weist das Ergebnis der zu merge() zu einem Vektor von INTs, result. Diese Zeile (die tatsächliche Zuweisung, nicht die Funktion) wirft a bad_alloc Fehler, und ich habe keine Ahnung warum.

Das Internet schlägt das vor bad_alloc wird größtenteils aufgrund von Memory-Fehlern geworfen, aber dies kann nicht der Fall sein, da das erste Mal, dass er angerufen wird 32-Bit int?). Ich gehe davon aus, dass ich für C ++ etwas Dummes und Falsches mache, aber ich weiß nicht was. Ich habe versucht anzurufen what() Auf die Ausnahme, aber das gibt nur seinen Namen zurück. Der Code:

vector<int> Sorting::mergeSort(vector<int> A) {

    // If the length of A is 0 or 1, it is sorted.
    if(A.size() < 2) return A;

    // Find the mid-point of the list.
    int midpoint = A.size() / 2;

    // Declare the left/right vectors.
    vector<int> left, right;

    // Declare the return vector.
    vector<int> result (A.size());

    for(int i = 0; i < midpoint; ++i) {
        left.push_back(A.at(i));
    }

    for(int i = midpoint; i < A.size(); ++i) {
        right.push_back(A.at(i));
    }

    left = mergeSort(left);
    right = mergeSort(right);
    result = merge(left, right);

    return result;

}


vector<int> merge(vector<int> left, vector<int> right) {

    vector<int> result;

    while(left.size() > 0 && right.size() > 0) {

        if(left.front() <= right.front()) {
            result.push_back(left.front());
            left.erase(left.begin());
        } else {
            result.push_back(right.front());
            right.erase(right.begin());
        }
    }

    if(left.size() > 0) {
        for(int i = 0; i < left.size(); ++i) {
            result.push_back(left.at(i));
        }
    } else {
        for(int i = 0; i < right.size(); ++i) {
            result.push_back(right.at(i));
        }
    }

}

Wenn ich das neu schreibe merge Funktion, nur einen Verweis auf result Und bearbeiten Sie es während der Funktion, es funktioniert einwandfrei, aber ich wollte den Code so nah wie möglich an den für den Zusammenführungsort angegebenen "Standard" -PsUedo-Code halten.

Ich schätze jede Hilfe, danke.

Answer 1

In dem Merge Funktion, vector<int> result wird nicht zurückgegeben.