如何动态分配全局int *？

Question

我正在尝试用C ++做一个Merge Sort代码，并且为了避免大量内存使用，我想将辅助向量声明为全局变量。您可能知道，使用全局变量策略时，使用的空间是O（1），而使用另一个时，它是O（N logN）。但是有一个小问题，我不知道将用于测试我的代码的向量的大小，所以我需要动态分配该全局变量。

我已经尝试过这样的事情：

这来自.h档案：

void mymergesort_recursive(std::vector<int> &v, SortStats &stats, int i = 0, 
                           int f = 0, bool nouveau = true);
int *aux = nullptr;

这来自.cpp存档：

void mymergesort_recursive(std::vector<int> &v, SortStats &stats, int i, 
                           int f, bool nouveau) {
    if (nouveau) {
        stats.recursive_calls = 1;
        f = int(v.size());
        // Allocates the variable aux according with the vector size. This makes a lot of memory economy.

        aux = new int[f];
    } else {
        ...
    }
    ...
}

实际上，我也试过这个：

aux = (int *)malloc(f * sizeof(int));

aux = static cast <int*>(malloc(f * sizeof(int)));

和其他尝试和错误的可能性都导致了同样的错误:-(

`到'的多重定义

我在这个论坛中已经找到了其他一些问题，但是尽管存在很多类似的问题，但我还是无法解决这个问题。

我认为已经清楚地解释了这个问题，但如果有什么模糊不清的话，请问。

Answer 1

错误是您在标头上声明了一个变量。

在标题上你应该放

extern int* aux;

然后在一些.cpp中你应该把：

int* aux= nullptr;

无论如何，你应该认真考虑使用int* aux代替std::vector<int> aux;。

• 它将为您保留元素数量
• 空的时候几乎不会使用任何空间。
• 它会根据需要增长。
• 在使用它来优化它之前，您可以使用reserve内存。
• 你不需要打电话给delete / free

Answer 2

使用全局辅助向量将不会实现O（1）内存空间开销，向量的大小将是您尝试排序的最大向量的大小（或者至少是智能实现的一半），因此O（N）空间高架。

此外，使用全局变量使代码不可重入，非线程安全，并在排序完成后保留开销。

这是一个更好的方法：

• 编写一个递归的mergesort_helper函数，该函数在合并阶段采用此临时数组来存储左子数组。
• 在mergesort函数中，分配一个大小为(N + 1) / 2元素的临时数组，并将其传递给递归的mergesort_helper函数。
• 释放临时数组
• 回到来电者。