合并排序 - 尝试分配向量时抛出 std::bad_alloc

Question

女士们先生们下午好。所以，今天不是我犯错误的日子。在 C++ 中实现合并排序（不是就地），我在代码上遇到了真正的麻烦，不知道为什么。 mergeSort() 函数的倒数第二行将 merge() 的结果分配给一个整数向量 result。这一行（实际分配，而不是函数）抛出一个 bad_alloc 错误，我不知道为什么。

互联网表明 bad_alloc 大多是由于内存不足错误而引发的，但事实并非如此，因为第一次调用它是在 500 个整数的向量上，这应该也相差甚远。很多内存（那是什么，比如 32 位 int 上的 2 Kb？）。我认为我在为 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 并在函数期间编辑它，它可以正常工作，但我想保留代码尽可能接近为合并排序给出的“标准”伪代码。

我很感激任何帮助，谢谢。

Answer 1

在Merge函数中，vector结果没有被返回。