C++迭代式归并排序vector出现double free or corruption (!prev)问题

问题描述 #

使用C++ vector实现迭代式归并排序时，发现当vector的大小n处于17到30之间时，会触发double free or corruption (!prev)错误；当n小于17或大于30时则无此错误。代码未手动调用free或delete操作，但仍出现堆内存错误。

错误原因 #

该错误本质是堆内存被越界访问破坏。虽然代码中没有手动管理内存，但vector内部依赖堆内存存储数据，当代码存在隐含的越界读写操作时，会破坏堆的内部管理结构，最终在程序退出（vector自动销毁）时触发double free或内存损坏错误。

具体到代码中的问题：

1. MergeSort循环逻辑缺陷：当n在17-30区间时，循环会执行到interval=32（大于vector大小）的MergePass操作。此时虽然不会触发Merge函数调用，但循环的交替读写逻辑可能导致临时vector与原vector的内容同步出现异常，间接破坏堆结构。
2. 边界条件判断不严谨：MergePass中k = v1.size() - 2 * interval + 1的计算方式存在隐含风险，当interval接近vector大小时，可能导致循环边界判断失误，引发潜在的越界访问。

代码修正方案 #

1. 修复MergeSort循环逻辑 #

确保最后一次排序结果始终写回原vector，避免不必要的大interval操作：

void MergeSort(vector<int> &v)
{
    int n = v.size();
    if (n <= 1) return;
    vector<int> temp(n);
    int interval = 1;
    bool to_temp = true;

    while (interval < n)
    {
        if (to_temp)
            MergePass(v, temp, interval);
        else
            MergePass(temp, v, interval);
        interval *= 2;
        to_temp = !to_temp;
    }

    // 若最后一次结果存在临时vector中，同步回原vector
    if (to_temp)
        v.swap(temp);
}

2. 修正MergePass边界判断 #

简化循环条件，避免复杂的边界计算：

void MergePass(vector<int> &v1, vector<int> &v2, int interval)
{
    int n = v1.size();
    int i = 0;
    // 合并完整的相邻子序列
    while (i <= n - 2 * interval)
    {
        Merge(v1, v2, i, i + interval - 1, i + 2 * interval - 1);
        i += 2 * interval;
    }
    // 处理剩余元素
    if (i < n - interval)
        Merge(v1, v2, i, i + interval - 1, n - 1);
    else
    {
        for (; i < n; i++)
            v2[i] = v1[i];
    }
}

原错误代码 #

#include <iostream>
#include <vector>
#include <cstdlib>
#include <random>
using namespace std;
// v1[left...middle] and v1[middle+1...right] are Ordered,merge them to v2;
void Merge(vector<int> &v1, vector<int> &v2, int left, int middle, int right)
{
    int i = left, j = left, k = middle + 1;
    while (i <= middle && k <= right)
    {
        if (v1[i] <= v1[k])
            v2[j] = v1[i++];
        else
            v2[j] = v1[k++];
        ++j;
    }
    while (i <= middle)
    {
        v2[j++] = v1[i++];
    }
    while (k <= right)
    {
        v2[j++] = v1[k++];
    }
}

// Merge adjacent subsequences of length interval in v1 into v2
void MergePass(vector<int> &v1, vector<int> &v2, int interval)
{
    int i = 0, k = v1.size() - 2 * interval + 1;
    while (i < k)
    {
        Merge(v1, v2, i, i + interval - 1, i + 2 * interval - 1);
        i += 2 * interval;
    }

    /*for (i = 0; i < v1.size() - 2 * interval + 1; i += 2 * interval)
    {
        Merge(v1, v2, i, i + interval - 1, i + 2 * interval - 1);
    }*/
    if (i < v1.size() - interval)
        Merge(v1, v2, i, i + interval - 1, v1.size() - 1);
    else
    {
        for (; i < v1.size(); i++)
        {
            v2[i] = v1[i];
        }
    }
}
void MergeSort(vector<int> &v)
{
    int k= v.size();
    vector<int> v1(k);
    int i = 1;
    while (i < v.size())
    {
        MergePass(v, v1, i);
        i *= 2;
        MergePass(v1, v, i);
        i *= 2;
    }
}

int main()
{
    
    vector<int> v;
    int n;
    cout << "input the size:";
    cin >> n;
    for (int j = 0; j < n; j++)
    {
        v.push_back(rand() % 1000 + 1);
    }
    MergeSort(v);
}

内容的提问来源于stack exchange，提问作者Stark James