Mergesort - std :: bad_alloc jeté en essayant de vecteur assign

Question

Bonjour mesdames et messieurs. Donc, ce n'est pas mon jour pour les erreurs. Mise en œuvre Mergesort (pas en place) en C ++, et je vais avoir du mal réel avec le code, avec aucune idée pourquoi. L'avant-dernière ligne de la fonction de mergeSort() affecte le résultat de la merge() à un vecteur d'entiers, result. Cette ligne (la répartition réelle, pas la fonction) renvoie une erreur bad_alloc, et je ne sais pas pourquoi.

L'Internet suggère que bad_alloc est jeté principalement due à l'extérieur de la mémoire des erreurs, mais cela ne peut pas être le cas comme la première fois son appelé est sur un vecteur de 500 ints, qui devrait être loin trop de mémoire (ce est que, comme 2 Ko sur un int?) 32 bits. Je suppose que je fais quelque chose de stupide et incorrect pour C ++, mais je ne sais pas quoi. J'ai essayé d'appeler what() à l'exception, mais renvoie simplement son nom. Le 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));
        }
    }

}

Si je re-écrire la fonction merge juste prendre une référence à result et de le modifier au cours de la fonction, il fonctionne très bien, mais je voulais garder le code le plus près possible du pseudo-code « standard » donnée pour fusion-tri.

Je vous remercie de toute aide, merci.

Answer 1

Dans la fonction Merge, vector<int> result n'est pas retourné.