c++ - c++内存分配错误

Question

我正在用 C++ 编写自下而上归并排序的代码，但是这个错误发生在我为指针分配内存的那一行，

void merge(int *a, int low, int high, int mid,int max)
{
   int i, j, k; 
   int *c=new int[max];   //error occurs here
   i = low;
   k = low;
   j = mid + 1;
   while (i <= mid && j <= high)
   {
       if (a[i] < a[j])
       {
           c[k] = a[i];
           k++;
           i++;
       }
       else
       {
           c[k] = a[j];
           k++;
           j++;

       }
   }
   while (i <= mid)
   {
       c[k] = a[i];

       k++;
       i++;
   }
   while (j <= high)
   {
       c[k] = a[j];
       k++;
       j++;
   }
   for (i = low; i < k; i++)
   {
       a[i] = c[i];
   }
}

问题是什么，好像没有更多可用内存了？？

Answer 1

你的腐败问题是这样的:

k = low;

您正在使用 k 作为临时数组的索引。它应该从 0 开始，而不是 low 将其更改为:

k = 0;

关于算法的其余部分，存在明显的内存泄漏。您没有删除临时阵列。此外，归并排序算法在 C 和 C++ 中比大多数语言要容易得多，正是因为它具有指针运算的 native 能力

例如:

template<typename T>
void merge(T* ar, size_t mid, size_t len)
{
    T *merged = new T[len]; // note. normally i would use a smart pointer

    size_t i=0, j=mid, k=0;
    while (i<mid && j<len)
    {
        if (ar[i] < ar[j])
            merged[k++] = ar[i++];
        else
            merged[k++] = ar[j++];
    }

    while (i < mid)
        merged[k++] = ar[i++];
    while (j < len)
        merged[k++] = ar[j++];

    std::copy(merged, merged+k, ar);
    delete [] merged;
}

template<typename T>
void mergesort(T* ar, size_t len)
{
    if (len<2)
        return;

    mergesort(ar, len/2);
    mergesort(ar+len/2, len-len/2);
    merge(ar, len/2, len);
}

使用上面的。下面演示了它是如何被调用的:

int main()
{
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<> dist(1,99);

    std::vector<int> data;
    data.reserve(25);
    std::generate_n(std::back_inserter(data), data.capacity(),
                    [&](){ return dist(rng);});

    for (auto x : data)
        std::cout << x << ' ';
    std::cout << '\n';

    mergesort(data.data(), data.size());

    for (auto x : data)
        std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

输出(明显不同)

55 39 40 87 49 1 94 8 20 47 42 23 93 99 81 52 17 66 3 6 74 5 49 13 67 
1 3 5 6 8 13 17 20 23 39 40 42 47 49 49 52 55 66 67 74 81 87 93 94 99 

综上所述，除非这是针对学术界的，否则不使用 std::sort 就太疯狂了

---

替代分配

自下而上的设计在不同的情况下效果很好，但它使用的内存分配系统对于大型集合来说是可怕的。对于 N 项目容器，所需的总临时空间永远不会超过 N 项目，因此您可以使用前端加载程序预先将其分配给实际合并然后，排序与合并算法一起提供临时空间供使用，而不是分配自己的临时空间。唯一棘手的部分是知道在 tmp 存储中的哪个位置可以安全使用空间。但你已经知道了。您用于排序序列的相同偏移量也可用于正确匹配的临时空间位置:

template<typename T>
void merge(T* ar, size_t mid, size_t len, T* tmp)
{
    size_t i=0, j=mid, k=0;
    while (i<mid && j<len)
    {
        if (ar[i] < ar[j])
            tmp[k++] = ar[i++];
        else
            tmp[k++] = ar[j++];
    }

    while (i < mid)
        tmp[k++] = ar[i++];
    while (j < len)
        tmp[k++] = ar[j++];

    std::copy(tmp, tmp+k, ar);
}


template<typename T>
void mergesort_int(T* ar, size_t len, T* tmp)
{
    if (len < 2)
        return;

    mergesort_int(ar, len/2, tmp);
    mergesort_int(ar+len/2, len-len/2, tmp+len/2);
    merge(ar, len/2, len, tmp);
}

template<typename T>
void mergesort(T* ar, size_t len)
{
    if (len<2)
        return;

    std::vector<T> tmp(len)
    mergesort_int(ar, len, &tmp[0]);
}

使用与前一个示例相同的main()，结果是相似的:

24 9 26 93 35 75 99 95 49 58 32 37 30 88 55 13 76 23 99 90 50 66 38 8 3 
3 8 9 13 23 24 26 30 32 35 37 38 49 50 55 58 66 75 76 88 90 93 95 99 99 

请记住，这现在需要一个 单个 分配 N 项(在我们的例子中，我们使用 vector 进行自动内存管理)然后在整个算法中使用。您会发现这相当更快，特别是对于大型数据集。