Mergesort - std :: bad_alloc lanciato quando si tenta di assegnare vettore

Question

Buon pomeriggio signore e signori. Quindi, non è il mio giorno per errori. Implementazione di Mergesort (non sul posto) in C ++ e ho veri problemi con il codice, senza avere idea del perché. La seconda a ultima linea del mergeSort() La funzione assegna il risultato del merge() a un vettore di int, result. Questa riga (l'allocazione effettiva, non la funzione) lancia a bad_alloc Errore, e non ho idea del perché.

Internet lo suggerisce bad_alloc è per lo più lanciato a causa di errori fuori memoria, ma questo non può essere il caso come la prima volta che si chiama su un vettore di 500 int, che non dovrebbe essere affatto vicino a troppa memoria (che cos'è, come 2 kb su a 32 bit int?). Presumo che sto facendo qualcosa di sciocco e errato per C ++, ma non so cosa. Ho provato a chiamare what() Per eccezione, ma questo restituisce il suo nome. Il codice:

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));
        }
    }

}

Se riscrivo il merge funzione a cui fare un riferimento a result E modificarlo durante la funzione, funziona bene, ma volevo mantenere il codice il più vicino possibile al code PSUDEDO "standard" dato per unione-Sort.

Apprezzo qualsiasi aiuto, grazie.

Answer 1

Nel Merge funzione, vector<int> result non viene restituito.