c++ - 合并排序程序总是有效，但有时会在最后说 abort trap

Question

我是一名初学者 C++ 程序员，刚刚开始学习算法/数据结构，并且正在阅读一本书来编写归并排序程序。将书中的 int 数组转换为 int vector 后，排序似乎仍然有效，但偶尔会在最后吐出错误。我似乎无法弄清楚为什么这种情况有时会发生。这就是它所说的:

mergesort_sa(36921,0x7fff74240000) malloc: *** error for object 0x7f879a500118: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

我在谷歌上搜索了“Abort trap: 6”，它说了一些关于写入我不拥有的内存的内容。我查看了我的程序，我认为我传递的左右边界是正确的，所以我不明白为什么要这样说。任何人都知道为什么会这样或者能够告诉我为什么它只是偶尔发生而不是每次运行都会发生？这是我的完整代码:

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int> &numbers, vector<int> &temp_numbers, int left, int mid, int right);
int l = 0, r = 0, m = 0;

void merge_sort(vector<int> &numbers, vector<int> &temp_numbers, int left, int right){     
    int mid;    

    if (right > left) {
        mid = (left+right)/2;
        cout << "LEFT SORT" << endl;
        l++;
        merge_sort(numbers, temp_numbers, left, mid);   
        cout << "RIGHT SORT"  << endl;
        r++;
        merge_sort(numbers, temp_numbers, mid+1, right); 
        cout << "MERGE" << endl;
        m++;
        merge(numbers, temp_numbers, left, mid+1, right);   
    }
}

void merge(vector<int> &numbers, vector<int> &temp_numbers, int left, int mid, int right){
    int i, left_end, size, temp_pos;
    left_end = mid - 1;
    temp_pos = left;
    size = right-left + 1;

    while ((left <= left_end) && (mid <= right)) {
        if (numbers[left] <= numbers[mid]) {
            temp_numbers[temp_pos] = numbers[left];
            temp_pos++;
            left++;
        }   
        else {
            temp_numbers[temp_pos] = numbers[mid];
            temp_pos++;
            mid++;
        }
    }
    while (left <= left_end) {
        temp_numbers[temp_pos] = numbers[left];
        left++;
        temp_pos++;
    }
    while (mid <= right) {
        temp_numbers[temp_pos] = numbers[mid];
        mid++;
        temp_pos++;
    }
    for (i = 0; i <= size; i++) {
        numbers[right] = temp_numbers[right];
        right--;
    }
}

int main(int argc, char *argv[]) {

    vector<int> numbers, temp_numbers;
    int x, n;

    // setup
    cout << "Enter numbers to sort separated by spaces. Press Ctrl+D when you are finished.\n\n";
    while(cin >> x) {
        numbers.push_back(x);
    }
    n = numbers.size();
    temp_numbers.resize(n);
    cout << "\nCount: " << n << endl << "Numbers to be sorted: ";
    for (int i = 0; i < n; i++)
        cout << numbers[i] << " ";
    cout << endl << endl << "Steps taken:\n";

    // sort
    merge_sort(numbers, temp_numbers, 0, n-1);

    // print
    cout << endl << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << numbers[i] << " ";
    cout << endl << endl << "left sorts: " << l << "  right sorts: " << r << "  merges: " << m << endl; 
    return 0;
}

Answer 1

当您将合并结果从临时空间复制回主空间时，有时会超出 vector 的范围。观察:

size = right-left + 1;

由于 right 和 left 索引是包含在内的，因此 size 包含要合并的子数组中的元素数。但是你这样做:

for (i = 0; i <= size; i++) {
    numbers[right] = temp_numbers[right];
    right--;
}

执行 size + 1 迭代，而您只想复制 size 元素。当 left 为 0 时，即在索引 -1 处访问 vector 边界外(下方)。

即使这没有产生内存错误，它也不会破坏您的数据，这完全是幸运的。这似乎是由于您首先对每个分区的左半部分进行递归，因此每当您有这种类型的溢出实际上是整个 vector 的边界时，临时空间中已经存在的值就是一个之前合并产生的，复制到主空间相应位置没有效果。