Mergesort - std :: bad_alloc, выбрасываемый при попытке назначить вектор - PullRequest
Новая
       3

Mergesort - std :: bad_alloc, выбрасываемый при попытке назначить вектор

3 голосов
/ 15 августа 2010

Добрый день, дамы и господа. Так что это не мой день для ошибок. Реализация Mergesort (не на месте) в C ++, и у меня есть реальные проблемы с кодом, без понятия почему. От последней до последней строки функции mergeSort() присваивается результат merge() вектору целых чисел result. Эта строка (фактическое распределение, а не функция) выдает ошибку bad_alloc, и я понятия не имею, почему.

Интернет предполагает, что bad_alloc в основном выбрасывается из-за ошибок нехватки памяти, но это не может быть так, так как первый раз, когда он вызывается для вектора 500 дюймов, который не должен находиться слишком близко к памяти (что это такое, как 2 Кбайт на 32-битном int?). Я предполагаю, что делаю что-то глупое и неправильное для C ++, но я не знаю что. Я попытался вызвать what() для исключения, но это просто возвращает его имя. Код: 

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

}

Если я переписываю функцию merge, чтобы просто взять ссылку на result и отредактировать ее во время функции, она работает нормально, но я хотел, чтобы код был как можно ближе к «стандартному» psuedo -код, заданный для сортировки слиянием.

Я ценю любую помощь, спасибо.

1 Ответ

3 голосов
/ 15 августа 2010

В функции Merge vector<int> result не возвращается.

...